E. Поменяй местами и возьми
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив из $$$n$$$ целых чисел. Вы должны сделать $$$n$$$ ходов.

Изначально у вас счет $$$0$$$.

На $$$i$$$-м ходе вы можете один раз поменять местами любые $$$2$$$ соседних элемента, а затем заменить ровно один из них на $$$0$$$. Или вы можете пропустить ход. В любом случае, после этого к вашему счету добавляется $$$a_i$$$.

Какой максимальный счет вы можете получить?

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$2 \le n \le 500$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Выходные данные

Выведите одно целое число — максимально возможный счет.

Примеры
Входные данные
2
3 1
Выходные данные
6
Входные данные
5
7 3 9 6 12
Выходные данные
52
Примечание

В первом примере чтобы получить максимальный счет, будем действовать следующим образом. Первый ход пропустим, к счету добавится $$$3$$$. На втором ходу поменяем местами первый и второй элемент, и заменим $$$1$$$ на $$$0$$$, к счету добавится $$$3$$$. Итоговый счет $$$6$$$.