Дано рядок \(S\) довжиною \(N\). Знайдіть максимальну довжину непорожнього рядка, що зустрічається двічі або більше в \(S\) як безперервні підрядки без перекриття.

Більш формально знайдіть максимальне ціле додатне число \(len\) таке, що існують цілі числа \(l_1\) і \(l_2\) (\( 1 \leq l_1, l_2 \leq N - len + 1\)), які задовольняють наступному:

• \(l_1 + len \leq l_2\)

• S[l_1 + i] = S[l_2 + i] (\(i = 0, 1, ..., len - 1\))

Якщо такого цілого числа \(len\) немає, то виведіть 0.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\) (\(2 \le N \le 5 \times 10^3\)).

Другий рядок містить \(S\) (\(|S| = N\)).

Формат вихідних даних

У вихідний потік вивести \(len\) або 0.

Примітка

До прикладу 1:

Рядки, що задовольняють умовам: \(a\), \(b\), \(ab\) і \(ba\).

Максимальна довжина серед них 2.

\(aba\) зустрічається двічі в \(S\) як суміжні підрядки, але немає пари цілих чисел \(l_1\) і \(l_2\), таких, що \(l_1 + len \leq l_2\).

Приклад вхідних даних

5
ababa

Приклад вихідних даних

2

Приклад вхідних даних

2
xy

Приклад вихідних даних

0

Приклад вхідних даних

13
strangeorange

Приклад вихідних даних

5