Po đang chơi một trò chơi tung xúc xắc.

Ban đầu, một con xúc xắc có \(10^{9}\) mặt được tung lên \(n\) lượt, trong lượt thứ \(i\) giá trị mặt trên của con xúc xắc là \(x_{i}\).

Po được chọn 3 số \(k,\ l,r\) cho biết Po chơi ở các lượt \(l,\ l + 1,l + 2,\ldots.,r - 1,\ r\). Nếu trong mỗi lượt chơi giá trị mặt trên của xúc xắc là \(k\) thì Po được gấp đôi số tiền đang có, ngược lại số tiền của Po bị giảm đi một nửa.

Hãy cho biết Po cần chọn 3 số \(k,l,r\ (1 \leq l \leq r \leq n)\) là bao nhiêu để số tiền nhận được là lớn nhất, biết rằng ban đầu Po có 1 đồng.

Dữ liệu vào:

+ Dòng đầu ghi số nguyên \(n\ (1 \leq n \leq 10^{5})\).

+ Dòng thứ 2 ghi lần lượt các số \(x_{1},x_{2},\ldots,x_{n}\ (1 \leq x_{i} \leq 10^{9})\).

Kết quả:

+ Ghi lần lượt 3 số \(k,l,r\) tìm được, nếu có nhiều kết quả thì ghi ra kết quả có \(l\) lớn nhất.

Ví dụ:

Giới hạn:

+ Có \(\frac{1}{3}\) số test có \(n \leq 500\)

+ Có \(\frac{1}{3}\) số test khác có \(n \leq 5000\);

+ Có \(\frac{1}{3}\) số test còn lại không có ràng buộc gì thêm