Cho dãy số nguyên dương ~A~. Hãy tìm một dãy con của dãy ~A~ có các tính chất:

• Không có ba số liên tiếp nào của dãy ban đầu có mặt trong dãy con

• Trong ba số liên tiếp của dãy ban đầu, có ít nhất 1 số có mặt trong dãy con

• Tổng các số hạng trong dãy con được chọn phải là lớn nhất có thể được.

Input

Dòng đầu tiên chứa số nguyên dương ~N~ ~(N ≤ 10^6)~

~N~ dòng tiếp theo, dòng ~i~ chứa số nguyên dương ~a_i~ ~(a_i ≤ 10^6)~

Output

Dòng thứ nhất là chứa hai số nguyên dương ~T~ và ~M~ là tổng các số trong dãy được chọn và số lượng các số hạng trong dãy được chọn.

~M~ dòng tiếp theo dòng thứ ~k~ ghi số ~j_k~ là chỉ số của số hạng được chọn thứ ~k~

Sample Test

Input

6
2
6
5
1
7
3

Output

21 4
2
3
5
6