Колода состоит из \(n\) карт. Изначально на \(i\)-й сверху карте написано число \(a_{i}\). Числа, записанные на картах, не изменяются.
Вы играете в следующую игру. Изначально ваш счёт равен \(0\). На каждом шаге вы производите одну из следующих операций:
- Выбрать нечётное\(^{\dagger}\) целое положительное число \(i\), не превосходящее числа карт в колоде на данный момент. Убрать \(i\)-ю сверху карту из колоды и прибавить число, записанное на этой карте, к вашему счёту. Оставшиеся карты нумеруются заново, начиная сверху.
- Выбрать чётное\(^{\ddagger}\) целое положительное \(i\), не превосходящее числа карт в колоде на данный момент. Убрать \(i\)-ю сверху карту из колоды. Оставшиеся карты нумеруются заново, начиная сверху.
- Завершить игру. Завершить игру можно в любой момент, вы не обязаны убирать все карты из изначальной колоды.
Чему равен максимальный счёт, который можно получить по окончании игры?
\(^{\dagger}\) Целое число \(i\) называется нечётным, если существует целое \(k\), такое что \(i = 2k + 1\).
\(^{\ddagger}\) Целое число \(i\) называется чётным, если существует целое \(k\), такое что \(i = 2k\).
Выходные данные
Для каждого набора входных данных выведите одно число — наибольший возможный счёт, достижимый к концу игры.
Примечание
В первом наборе входных данных можно получить итоговый счёт \(5\) следующим образом:
- На первом шаге выбрать \(i=2\). Счёт остаётся равным \(0\), а числа, записанные на картах, образуют последовательность \([-4, -3, 5]\).
- На втором шаге выбрать \(i=3\). Счёт становится равным \(5\), а числа, записанные на картах, образуют последовательность \([-4, -3]\).
- На третьем шаге завершить игру с итоговым счётом \(5\).
Во втором наборе входных данных можно получить итоговый счёт \(4\) следующим образом:
- На первом шаге выбрать \(i=3\). Счёт становится равным \(3\), а числа, записанные на картах, образуют последовательность \([1, -2, -4]\).
- На втором шаге выбрать \(i=1\). Счёт становится равным \(4\), а числа, записанные на картах, образуют последовательность \([-2, -4]\).
- На третьем шаге завершить игру с итоговым счётом \(4\).
В третьем наборе входных данных можно получить итоговый счёт \(2\) следующим образом:
- На первом шаге выбрать \(i=1\). Счёт становится равным \(-1\), а числа, записанные на картах, образуют последовательность \([3, -5]\).
- На втором шаге выбрать \(i=1\). Счёт становится равным \(2\), а числа, записанные на картах, образуют последовательность \([-5]\).
- На третьем шаге завершить игру с итоговым счётом \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
-4 1 -3 5
4
1 -2 3 -4
3
-1 3 -5
1
-1
|
5
4
2
0
|