TWICE - Twice

no tags 

Given a string S, find the longest substring that appears at least twice in S (occurrences may overlap).

Input

The first line contains an integer L (1 ≤ L ≤ 200000), the length of S.

The second line contains the string S, consisting of exactly L lowercase letters ('a'-'z').

Output

Output the length of the longest substring that appears at least twice in S. If there is no such substring, output 0.

Example

Input:
11
sabcabcfabc

Output:
3

Input:
18
trutrutiktiktappop

Output:
4

hide comments
Ajey Golsangi: 2012-09-05 17:32:24

Nice problem.

Buda IM (retired): 2012-02-25 22:59:20

Suffix array is not needed to solve this problem

Nikhil Garg: 2010-12-27 17:14:08

Too bad - I don't know O(N) construction of suffix tree yet :(

Lovro Puzar: 2009-08-24 14:52:50

> is substring of length 1 is also considered??

Sure.


Added by:Lovro Puzar
Date:2009-08-21
Time limit:0.151s-0.418s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Own problem