Let's say that the sequence of strings t
1 , ..., t
k is a journey of length k if for all i > 1 t
i< /sub> is a substring of ti - 1 of strictly less length. For example, { ab , b } is a journey, and { ab , c } or { a , a } — no.
Define a string traversal s as a traversal t1 , ..., tk , all of whose strings can be nested in s such that there are (possibly empty) strings u1 , ..., uk + 1 such that s = u1t1 u2 t2 ... uk tk uk +&thinsp ;1 . For example, { ab , b } is a string travel for abb , but not for bab , since the corresponding substrings are from right to left.
Let's call the length of the journey the number of lines of which it consists. Determine the maximum possible travel length along the given string s .
Input
The first line contains an integer n ( 1 ≤ n ≤ 500 000 ) — length of string s .
The second line contains the string s , consisting of n lowercase English letters.
Imprint
Print one number — the longest travel length in string s .
Note
In the first example, the longest string traversal is { abcd , bc , c } .
In the second example, { bb , b } would be appropriate.
Examples
| # |
Input |
Output |
| 1 |
7
abcdbcc |
3 |
| 2 |
4
bbcb |
2 |