Cho một xâu \(s\) có độ dài \(n\), chỉ gồm các chữ cái in hoa từ A đến Z.

Một đoạn con liên tiếp \([l, r]\) của xâu được gọi là tốt nếu tồn tại một kí tự xuất hiện nhiều hơn một nửa độ dài đoạn đó.

Nói cách khác, gọi \(cnt(c, l, r)\) là số lần xuất hiện của kí tự \(c\) trong đoạn \([l, r]\). Đoạn \([l, r]\) là tốt nếu tồn tại một kí tự \(c\) sao cho:

Yêu cầu

Hãy tìm độ dài lớn nhất của một đoạn tốt trong xâu \(s\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^5\)), là độ dài xâu.
• Dòng thứ hai chứa xâu \(s\) có độ dài \(n\), chỉ gồm các chữ cái in hoa từ A đến Z.

Output

• In ra một số nguyên duy nhất là độ dài lớn nhất của một đoạn tốt.

Example

7
AABBBCC

5

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(30\%\) số điểm): Xâu \(s\) chỉ gồm hai kí tự A và B.
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.