Tần số

Cho một xâu kí tự \(S\) chỉ gồm các chữ cái la tinh in thường từ a, …, z.

Một xâu con \(X\) (gồm các kí tự ở vị trí liên tiếp) của \(S\) được gọi là một xâu có tần số xuất hiện cao nếu trong xâu \(X\) có một kí tự bất kì nào đó mà số lần xuất hiện của kí tự đó nhiều hơn tổng số lần xuất hiện của các kí tự còn lại trong xâu \(X\).

Ví dụ: với xâu \(S =\) “abbbabced”, xâu con \(X =\) “abbbabc” là một xâu có tần số xuất hiện cao, vì kí tự b xuất hiện \(4\) lần, tổng số lần xuất hiện của các kí tự còn lại bằng \(3\) (a xuất hiện \(2\) lần, c xuất hiện \(1\) lần).

Nếu xâu con \(X =\) “abbbabce”, kí tự b xuất hiện nhiều nhất là \(4\) lần, tổng số lần xuất hiện của các kí tự còn lại bằng \(4\) (a xuất hiện \(2\) lần, c xuất hiện \(1\) lần, e xuất hiện \(1\) lần). Do vậy xâu \(X =\) “abbbabce” không phải là một xâu có tần số xuất hiện cao.

Yêu cầu. Tìm xâu con \(X\) (gồm các kí tự ở vị trí liên tiếp) của xâu \(S\) mà là xâu có tần số xuất hiện cao và có độ dài lớn nhất.

Input

Input gồm một xâu \(S\) chỉ gồm các kí tự chữ cái la tinh in thường và có độ dài không lớn hơn \(2 \cdot 10^5\).

Output

Ghi ra đáp án là một số nguyên duy nhất là độ dài của xâu \(X\) tìm được.

Input

%
aaa

Output

%
3

Input

%
ababab

Output

%
5

Notes

Ta có thể chọn xâu \(X\) thỏa mãn yêu cầu là “aaa”.

Ta có thể chọn xâu \(X\) thỏa mãn yêu cầu là:

• \(X =\) “ababa” vì kí tự a xuất hiện \(3\) lần, số kí tự còn lại là \(2\); hoặc
• \(X =\) “babab” vì kí tự b xuất hiện \(3\) lần, số kí tự còn lại là \(2\).

Scoring

• (30%) Xâu \(S\) chỉ gồm các kí tự thuộc tập $ {a, b, c}$ và có độ dài không quá \(2 \cdot 10^3\);
• (30%) Xâu \(S\) chỉ gồm các kí tự chữ cái la tinh in thường có độ dài không quá \(2 \cdot 10^3\);
• (40%) Xâu \(S\) chỉ gồm các kí tự chữ cái la tinh in thường có độ dài không quá \(2 \cdot 10^5\).