Знищіть масив

Дано масив з $n$ цілих чисел $a_1,a_2,\dots ,a_n$.

Ви можете виконувати наступні операції:

• Вибрати або перший, або останній елемент та видалити його з масиву.

• Вибрати не перший та не останній елемент, замінити його сумою двох сусідніх елементів, видалити два сусідні елементи.

Зробіть так, щоб залишився лише один елемент з максимальним значенням.

Input

Перший рядок містить одне ціле число $n$ ($1\le n\le 1000$) — кількість елементів.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($|a_i|\le 10^9$) — елементи.

Output

У першому рядку виведіть максимальне значення останнього числа.

У другому рядку виведіть $t$ — кількість операцій.

У кожному з наступних $t$ рядків виведіть по одному число — індексу числа, над яким потрібно виконати операцію. Потрібно вивести не початковий індекс, а у момент часу перед виконання операції. Індексації з $1$.

Examples