C. Карточная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Колода состоит из $$$n$$$ карт. Изначально на $$$i$$$-й сверху карте написано число $$$a_{i}$$$. Числа, записанные на картах, не изменяются.

Вы играете в следующую игру. Изначально ваш счёт равен $$$0$$$. На каждом шаге вы производите одну из следующих операций:

  • Выбрать нечётное$$$^{\dagger}$$$ целое положительное число $$$i$$$, не превосходящее числа карт в колоде на данный момент. Убрать $$$i$$$-ю сверху карту из колоды и прибавить число, записанное на этой карте, к вашему счёту. Оставшиеся карты нумеруются заново, начиная сверху.
  • Выбрать чётное$$$^{\ddagger}$$$ целое положительное $$$i$$$, не превосходящее числа карт в колоде на данный момент. Убрать $$$i$$$-ю сверху карту из колоды. Оставшиеся карты нумеруются заново, начиная сверху.
  • Завершить игру. Завершить игру можно в любой момент, вы не обязаны убирать все карты из изначальной колоды.

Чему равен максимальный счёт, который можно получить по окончании игры?

$$$^{\dagger}$$$ Целое число $$$i$$$ называется нечётным, если существует целое $$$k$$$, такое что $$$i = 2k + 1$$$.

$$$^{\ddagger}$$$ Целое число $$$i$$$ называется чётным, если существует целое $$$k$$$, такое что $$$i = 2k$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \le a_i \le 10^{9}$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^{5}$$$.

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

Для каждого набора входных данных выведите одно число — наибольший возможный счёт, достижимый к концу игры.

Пример
Входные данные
4
4
-4 1 -3 5
4
1 -2 3 -4
3
-1 3 -5
1
-1
Выходные данные
5
4
2
0
Примечание

В первом наборе входных данных можно получить итоговый счёт $$$5$$$ следующим образом:

  1. На первом шаге выбрать $$$i=2$$$. Счёт остаётся равным $$$0$$$, а числа, записанные на картах, образуют последовательность $$$[-4, -3, 5]$$$.
  2. На втором шаге выбрать $$$i=3$$$. Счёт становится равным $$$5$$$, а числа, записанные на картах, образуют последовательность $$$[-4, -3]$$$.
  3. На третьем шаге завершить игру с итоговым счётом $$$5$$$.

Во втором наборе входных данных можно получить итоговый счёт $$$4$$$ следующим образом:

  1. На первом шаге выбрать $$$i=3$$$. Счёт становится равным $$$3$$$, а числа, записанные на картах, образуют последовательность $$$[1, -2, -4]$$$.
  2. На втором шаге выбрать $$$i=1$$$. Счёт становится равным $$$4$$$, а числа, записанные на картах, образуют последовательность $$$[-2, -4]$$$.
  3. На третьем шаге завершить игру с итоговым счётом $$$4$$$.

В третьем наборе входных данных можно получить итоговый счёт $$$2$$$ следующим образом:

  1. На первом шаге выбрать $$$i=1$$$. Счёт становится равным $$$-1$$$, а числа, записанные на картах, образуют последовательность $$$[3, -5]$$$.
  2. На втором шаге выбрать $$$i=1$$$. Счёт становится равным $$$2$$$, а числа, записанные на картах, образуют последовательность $$$[-5]$$$.
  3. На третьем шаге завершить игру с итоговым счётом $$$2$$$.