A12074 | String Journey

We call a sequence of strings $t_{1},...,t_{k}$ a journey of length $k$ , if for each $i>1$ $t_{i}$ is a substring of $t_{i-1}$ and length of $t_{i}$ is strictly less than length of $t_{i-1}$ . For example, ${ab,b}$ is a journey, but ${ab,c}$ and ${a,a}$ are not.

Define a journey on string $s$ as journey $t_{1},...,t_{k}$ , such that all its parts can be nested inside $s$ in such a way that there exists a sequence of strings $u_{1},...,u_{k+1}$ (each of these strings can be empty) and $s=u_{1}t_{1}u_{2}t_{2}...\ u_{k}t_{k}u_{k+1}$ . As an example, ${ab,b}$ is a journey on string $abb$ , but not on $bab$ because the journey strings $t_{i}$ should appear from the left to the right.

The length of a journey on a string is the number of strings in it. Determine the maximum possible length of a journey on the given string $s$ .

The first line contains a single integer $n$ ( $1<=n<=500000$ ) — the length of string $s$ .

The second line contains the string $s$ itself, consisting of $n$ lowercase Latin letters.

Print one number — the maximum possible length of string journey on $s$ .