Вам дан массив из \(n\) целых чисел. Вы должны сделать \(n\) ходов.
Изначально у вас счет \(0\).
На \(i\)-м ходе вы можете один раз поменять местами любые \(2\) соседних элемента, а затем заменить ровно один из них на \(0\). Или вы можете пропустить ход. В любом случае, после этого к вашему счету добавляется \(a_i\).
Какой максимальный счет вы можете получить?
Выходные данные
Выведите одно целое число — максимально возможный счет.
Примечание
В первом примере чтобы получить максимальный счет, будем действовать следующим образом. Первый ход пропустим, к счету добавится \(3\). На втором ходу поменяем местами первый и второй элемент, и заменим \(1\) на \(0\), к счету добавится \(3\). Итоговый счет \(6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 1
|
6
|
|
2
|
5
7 3 9 6 12
|
52
|