Nguồn: Học sinh Giỏi THPT Hà Nội năm 2023 - 2024

An có một xâu ký tự \(S\) có độ dài \(N\), chỉ gồm các chữ cái Latin in thường. An muốn tìm một xâu con liên tiếp không rỗng của xâu \(S\) sao cho chênh lệch giữa số lần ký tự xuất hiện nhiều nhất và số lần ký tự xuất hiện ít nhất ở trong xâu con là lớn nhất. Lưu ý rằng, ký tự xuất hiện ít nhất phải xuất hiện ít nhất một lần trong xâu con.

Input

Dữ liệu vào từ tệp văn bản CHENHLECH.INP:

• Dòng đầu tiên chứa số nguyên \(N\) \((1\le N\le 10^6)\) là độ dài của xâu \(S\);
• Dòng thứ hai chứa xâu \(S\).

Output

Kết quả ra tệp văn bản CHENHLECH.OUT:

• Một số nguyên duy nhất là chênh lệch lớn nhất của xâu con tìm được.

Examples

6
caabac

2

3
ttt

0

Note

• Ví dụ 1: Có thể chọn xâu con: aaba hoặc caaba hoặc aabac hoặc caabac.
• Ví dụ 2: Có thể chọn xâu con: ttt hoặc tt hoặc t.

Constraint

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài thoả mãn: \(N \le 10^2\);
• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thoả mãn: \(N \le 10^5\);
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.