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