Дано масив з $n$ цілих чисел $a_1, a_2, \dots, a_n$. Ви можете виконувати наступні операції: \begin{itemize} \item Вибрати або перший, або останній елемент та видалити його з масиву. \item Вибрати не перший та не останній елемент, замінити його сумою двох сусідніх елементів, видалити два сусідні елементи. \end{itemize} Зробіть так, щоб залишився лише один елемент з максимальним значенням. \InputFile Перший рядок містить одне ціле число $n$ ($1 \leq n \leq 1\,000$)~--- кількість елементів. Другий рядок містить $n$ цілих чисел $a_1, a_2, \dots, a_n$ ($|a_i| \leq 10^9$)~--- елементи. \OutputFile У першому рядку виведіть максимальне значення останнього числа. У другому рядку виведіть $t$~--- кількість операцій. У кожному з наступних $t$ рядків виведіть по одному число~--- індексу числа, над яким потрібно виконати операцію. Потрібно вивести не початковий індекс, а у момент часу перед виконання операції. Індексації з $1$.