COCI 2006/2007, Contest #5

Task DVAPUT

Ivana won the bet (Zvonko hadn't foreseen this and suspects that it is due to outside interference) and now Zvonko is waiting for her at the movies. While he is waiting, he is observing messages on a screen above him.

As Ivana is running late, Zvonko has been looking at the screen for a while and noticed that some messages appeared on the screen more than once. Naturally, he's been writing down all messages on a piece of paper. He wants to know the length of the longest string that appeared at least twice (appears in two different positions on the paper).

Input

The first line of input contains an integer L (1 ≤ L ≤ 200 000), the length of the string Zvonko wrote down.

The second line contains a string of L lowercase letter of the English alphabet.

Output

Output the length of the longest string that appears twice on a single line. If there is no such string, output zero.

Sample Tests

Input

11
sabcabcfabc

Output

3

Input

18
trutrutiktiktappop

Output

4

Input

6
abcdef

Output

0

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 14, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...