Nông dân John đã ra ngoài đi dạo dọc con đường và giờ ông nghĩ rằng có lẽ mình đã bị lạc!

Dọc con đường có \(N\) trang trại (\(1 \leq N \leq 100\)) nằm liên tiếp thành một hàng. Thật không may, các trang trại không có số nhà, khiến Nông dân John khó xác định vị trí của mình trên đường. Tuy nhiên, mỗi trang trại đều có một hộp thư đầy màu sắc bên đường, vì vậy Nông dân John hy vọng rằng nếu quan sát màu sắc của những hộp thư gần mình nhất, ông có thể xác định duy nhất vị trí hiện tại.

Mỗi màu hộp thư được biểu thị bằng một chữ cái trong phạm vi A..Z, vì vậy dãy \(N\) hộp thư dọc con đường có thể được biểu diễn bằng một xâu độ dài \(N\) gồm các chữ cái trong phạm vi A..Z. Một số hộp thư có thể cùng màu với những hộp thư khác. Nông dân John muốn biết giá trị nhỏ nhất của \(K\) sao cho khi quan sát bất kỳ dãy \(K\) hộp thư liên tiếp nào, ông đều có thể xác định duy nhất vị trí của dãy đó trên đường.

Ví dụ, giả sử dãy hộp thư dọc con đường là ABCDABC. Nông dân John không thể chọn \(K=3\), vì nếu nhìn thấy ABC, có hai vị trí khả dĩ trên đường mà dãy màu liên tiếp này có thể xuất hiện. Giá trị nhỏ nhất của \(K\) thỏa mãn là \(K=4\), vì nếu ông quan sát bất kỳ nhóm 4 hộp thư liên tiếp nào, dãy màu này sẽ xác định duy nhất vị trí của ông trên đường.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), và dòng thứ hai chứa một xâu gồm \(N\) ký tự, mỗi ký tự thuộc phạm vi A..Z.

Dữ liệu ra

In một dòng chứa một số nguyên duy nhất, là giá trị nhỏ nhất của \(K\) giải quyết được bài toán của Nông dân John.

Ví dụ

7
ABCDABC

4

Nguồn

USACO 2019 December Contest, Bronze - Where Am I?: https://usaco.org/index.php?page=viewproblem2&cpid=964

Tác giả: Brian Dean.