Xâu con dài nhất

Cho xâu \(S\) chỉ chứa các kí tự chữ cái tiếng Anh viết thường. Một xâu con của \(S\) là một dãy các kí tự liên tiếp trong xâu \(S\). Ví dụ, cd'' là một xâu con củaabcde'' còn ``ac'' thì không.

Hãy tính độ dài xâu con dài nhất mà xuất hiện ít nhất hai lần trong \(S\).

Input

• Dòng 1: gồm một số nguyên \(N\) (\(1 \le N \le 200\,000\)) là độ dài của xâu \(S\).

• Dòng 2: gồm \(N\) chữ cái tiếng Anh viết thường mô tả xâu \(S\).

Ràng buộc:

• Subtask 1: \(20\%\) số điểm, \(N \le 3\);

• Subtask 2: \(60\%\) số điểm, \(N \le 200\);

• Subtask 3: \(20\%\) số điểm còn lại không có thêm ràng buộc bổ sung.

Output

Ghi ra một số nguyên là độ dài xâu con dài nhất xuất hiện ít nhất hai lần trong \(S\). Nếu không có xâu con nào thỏa mãn, in ra số \(0\).

Example 1

Input:

3
aba

Output:

1

Example 2

Input:

3
abc

Output:

0

Example 3

Input:

10
abcabckabc

Output:

3

Example 4

Input:

19
chuchucikciklolipop

Output:

4

Note

Ví dụ 1: xâu con ``a'' xuất hiện hai lần, đây là xâu con dài nhất thỏa mãn.

Ví dụ 2: không có xâu con nào xuất hiện ít nhất hai lần.

Ví dụ 3: xâu con ``abc'' xuất hiện ba lần, đây là xâu con dài nhất thỏa mãn.

Ví dụ 4: xâu con ``chuc'' xuất hiện hai lần, đây là xâu con dài nhất thỏa mãn.