Cho dãy số nguyên a₁, a₂, .., a_n.

Yêu cầu: Hãy tìm một dãy con tăng có tổng lớn nhất của dãy.

Input

Gồm 2 dòng:
Dòng đầu là số nguyên dương n (n ≤ 5000).
Dòng sau gồm n số, mỗi số là một số nguyên a_i của dãy (-10000 ≤ a_i ≤ 10000, 1 ≤ i ≤ n).

Output

Gồm 2 dòng:
Dòng đầu là tổng lớn nhất tìm được.
Dòng thứ hai ghi số nguyên dương k là số lượng phần tử của dãy con.
Dòng sau ghi k số là chỉ số các phần tử thuộc dãy con.

Ví dụ

Input
10
5 2 3 4 1 99 5 6 7 8

Output
108
4
2 3 4 6