Xét dãy số nguyên không âm \(a_{1}, a_{2}, \ldots, a_{n}\). Một đoạn con của dãy được mô tả bằng hai chỉ số \(1 \leq L \leq R \leq n\) là dãy \(a_{L}, a_{L + 1}, \ldots, a_{R}\), đoạn con này có độ dài là \(R - L + 1\) và được gọi là xuất hiện ở vị trí \(p\) nếu \(a_{L} = a_{p}, a_{L + 1} = a_{p + 1}, \ldots, a_{R} = a_{p + R - L}\) \((p + R - L \leq n)\).

Yêu cầu: Cho dãy số nguyên không âm \(a_{1}, a_{2}, \ldots, a_{n}\), hãy tìm đoạn con xuất hiện nhiều nhất, nếu có nhiều đoạn con xuất hiện nhiều nhất chọn đoạn có độ dài lớn nhất, nếu vẫn có nhiều đoạn thỏa mãn thì chọn đoạn xuất hiện cuối cùng (có \(L\) lớn nhất).

Input

• Dòng thứ nhất chứa số nguyên dương \(n\) \((1 \leq n \leq 10^{5})\).
• Dòng thứ hai chứa số nguyên không âm \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\).

Output

• In ra hai số nguyên dương \(L, R\) mô tả đoạn con tìm được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 200\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 2000\).
• Subtask \(3\) (\(25\%\) số điểm): \(0 \leq a_{i} \leq 1\).
• Subtask \(4\) (\(25\%\) số điểm): không có rằng buộc gì thêm.

Example

4
0 1 0 1

3 4

9
0 1 2 0 1 2 0 2 0

9 9