Chênh lệch

An có một xâu ký tự \(S\) độ 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:

• 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\).

Ràng buộc:

• 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.

Output

In ra

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.

Example 1

Input:

6
caabac

Output:

2

Example 2

Input:

3
ttt

Output:

0

Note

Ở ví dụ thứ nhất, có thể chọn xâu con aaba`'' hoặccaaba'' hoặc ```aabac'' hoặc caabac`''. Chẳng hạn trongaaba'', ký tựaxuất hiện $3$ lần, ký tựb` xuất hiện \(1\) lần nên chênh lệch là \(3 - 1 = 2\), và không có xâu con nào cho chênh lệch lớn hơn.

Ở ví dụ thứ hai, mọi xâu con chỉ gồm một loại ký tự t nên số lần xuất hiện nhiều nhất bằng số lần xuất hiện ít nhất, chênh lệch bằng \(0\) (ví dụ chọn ttt`'',tt'' hoặc ```t'').