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 sẽ chơi ở các lượt ~l,l+1,l+2,….,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≤l≤r≤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≤n≤5.10^5)~.
• Dòng thứ 2 ghi lần lượt các số ~x_1,x_2,…,x_n~ ~(1≤x_i≤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à ~r~ lớn nhất.

**Ràng buộc: **

• Có ~1/3~ số test có ~n≤500~;
• Có ~1/3~ số test khác có ~n≤5000~;
• Có ~1/3~ số test còn lại không có ràng buộc gì thêm

Ví dụ:

Input 0

5
4 4 3 4 4 

Output 0

4 1 5 

Input 1

5
11 1 11 1 11 

Output 1

11 5 5