Prefixuffix

In this problem we only consider strings made of lowercase letters of the English alphabet. An initial fragment of a string is called a prefix, and a final fragment is called a suffix. In particular, the empty string is both a prefix and a suffix of every string.

Two strings are cyclically equivalent when one can be turned into the other by taking some suffix of it and moving that suffix from the end to the front. For example, ababba and abbaab are cyclically equivalent, whereas ababba and ababab are not. Every string is cyclically equivalent to itself.

You are given a string $t$ of length $n$. Find a prefix $p$ and a suffix $s$ of $t$, both of the same length, such that:

• $p$ and $s$ are cyclically equivalent,
• their common length is at most $\frac{n}{2}$ (so that $p$ and $s$ do not overlap in $t$), and
• their common length is as large as possible.

The first line contains one integer $n$, the length of the string $t$. ($1 \le n \le 10^6$)

The second line contains the string $t$ itself, consisting of $n$ lowercase letters of the English alphabet.

Print one integer: the largest common length of a prefix $p$ and a suffix $s$ that satisfy the conditions above.