Вам дан массив из \(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\)).
Выведите одно целое число — максимально возможный счет.
В первом примере чтобы получить максимальный счет, будем действовать следующим образом. Первый ход пропустим, к счету добавится \(3\). На втором ходу поменяем местами первый и второй элемент, и заменим \(1\) на \(0\), к счету добавится \(3\). Итоговый счет \(6\).
2 3 1
6
5 7 3 9 6 12
52
2000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач