Chuỗi hoán vị đối xứng (Palindromic-Permutation Substring)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho xâu $S=S_1S_2\ldots S_N$ gồm các chữ cái Latinh thường. Một đoạn con liên tiếp $S_LS_{L+1}\ldots S_R$ được gọi là tốt nếu có thể hoán vị các ký tự trong đoạn để tạo thành một xâu đối xứng.

Hãy tìm độ dài lớn nhất của một đoạn tốt. Nếu có nhiều đoạn tốt dài nhất, chọn đoạn có chỉ số đầu $L$ nhỏ nhất.

Input

• Dòng đầu chứa số nguyên $N$.
• Dòng thứ hai chứa xâu $S$ gồm đúng $N$ ký tự từ a đến z.

Output

In hai số nguyên LEN L, trong đó LEN là độ dài lớn nhất và $L$ là chỉ số đầu nhỏ nhất của một đoạn tối ưu.

Subtask

• Subtask 1 — 40%: $1\le N\le 2000$; $S$ gồm đúng $N$ chữ cái Latinh thường từ a đến z.
• Subtask 2 — 60%: $1\le N\le 2\cdot 10^5$; $S$ gồm đúng $N$ chữ cái Latinh thường từ a đến z.

Ví dụ

Ví dụ 1

Input

7
abacaba

Output

7 1

Giải thích

Toàn bộ xâu có số lần xuất hiện lẻ của đúng một ký tự nên có thể hoán vị thành xâu đối xứng.

Ví dụ 2

Input

5
abcde

Output

1 1

Giải thích

Mọi đoạn có độ dài ít nhất $2$ đều có ít nhất hai ký tự xuất hiện lẻ.