Trạm quan sát nhận được một chuỗi tín hiệu gồm các chữ cái thường. Một đoạn tín hiệu được gọi là lặp nếu đoạn đó xuất hiện ít nhất hai lần trong chuỗi, các lần xuất hiện có thể chồng lên nhau.

Cho xâu tín hiệu ~s~ độ dài ~n~. Hãy tìm độ dài lớn nhất của một đoạn tín hiệu lặp.

Yêu cầu

Tìm số nguyên lớn nhất ~L~ sao cho tồn tại hai vị trí bắt đầu khác nhau ~i~ và ~j~ mà:

~s[i..i+L-1] = s[j..j+L-1]~.

Nếu không có đoạn lặp không rỗng, in ~0~.

Dữ liệu

Dữ liệu vào từ chuẩn gồm:

• Dòng đầu tiên chứa số nguyên ~n~.
• Dòng thứ hai chứa xâu ~s~ gồm đúng ~n~ chữ cái tiếng Anh thường.

Kết quả

Ghi ra một số nguyên duy nhất là độ dài lớn nhất của một đoạn tín hiệu lặp.

Ví dụ

Ví dụ 1

Input

6
banana

Output

3

Ví dụ 2

Input

10
qwertyuiop

Output

0

Giải thích

Ví dụ 1

Đoạn ~\text{ana}~ xuất hiện tại các vị trí bắt đầu ~2~ và ~4~, nên đáp án ít nhất là ~3~. Không có đoạn lặp nào dài hơn.

Ví dụ 2

Không có ký tự nào xuất hiện hai lần, nên không có đoạn lặp không rỗng.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 2 \cdot 10^5~.
• ~s~ chỉ gồm các chữ cái tiếng Anh thường từ ~\text{a}~ đến ~\text{z}~.

Chấm điểm

• Subtask~1~ ~(25\%)~: ~n \le 500~.
• Subtask~2~ ~(35\%)~: ~n \le 5000~.
• Subtask~3~ ~(40\%)~: không có ràng buộc bổ sung.