Chị Hằng và chú Cuội đang cảm thấy cô đơn và nhớ trái đất. Họ muốn gửi thông điệp là một số nguyên \(x\) về trái đất, nhưng được mã hóa dưới dạng một xâu \(s\) độ dài \(n\). Giá trị của \(x\) là độ dài lớn nhất của xâu con \(t\) mà khi xóa đi phần xâu \(t\) trong \(s\) thì tồn tại cách sắp xếp các kí tự còn lại để tạo thành một xâu \(s'\) mà tồn tại xâu con của \(s'\) bằng xâu \(t\).

• Một xâu \(t\) được gọi là xâu con của \(s\) nếu ta có thể nhận được \(t\) bằng cách xóa đi một vài kí tự ở đầu (hoặc không xóa kí tự nào) và một vài kí tự ở cuối (hoặc không xóa) của xâu \(s\).

Thu may mắn là người được chọn để nhận thông điệp từ chị Hằng và chú Cuội. Tuy nhiên Thu không biết cách tìm ra giá trị \(x\) được mã hóa, bạn hãy giúp Thu tìm nó nhé.

Input

• Dòng thứ nhất gồm số nguyên dương \(n\) là độ dài xâu \(s\) (\(n \leq 5\cdot 10^6\)).
• Dòng thứ hai chứa xâu \(s\), chỉ gồm các kí tự chữ cái latin thường.

Output

• Gồm một dòng duy nhất là giá trị \(x\) tìm được.

Example

7
cabcbab

3

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n \leq 200\).
• Subtask 2 (\(30\%\) số điểm): \(n \leq 2000\).
• Subtask 3 (\(30\%\) số điểm): \(n \leq 10^5\).
• Subtask 4 (\(20\%\) số điểm): Không có ràng buộc gì thêm.