D. Максимальная сумма на четных позициях
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Индексы элементов массива начинаются с нуля (то есть первый элемент — это $$$a_0$$$, второй — $$$a_1$$$, и так далее).

Вы можете развернуть не более одного подмассива (последовательного отрезка) этого массива. Напомним, что подмассив $$$a$$$ с границами $$$l$$$ и $$$r$$$ равен $$$a[l; r] = a_l, a_{l + 1}, \dots, a_{r}$$$.

Ваша задача — развернуть такой подмассив, чтобы сумма элементов на четных позицияx получившегося массива была максимально возможной (то есть сумма элементов $$$a_0, a_2, \dots, a_{2k}$$$ для целого числа $$$k = \lfloor\frac{n-1}{2}\rfloor$$$ должна быть максимально возможной).

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину $$$a$$$. Вторая строка набора содержит $$$n$$$ целых чисел $$$a_0, a_1, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — это $$$i$$$-й элемент $$$a$$$.

Гарантируется, что сумма $$$n$$$ не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

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

Для каждого набора тестовых данных выведите ответ на отдельной строке — максимально возможная сумма элементов на четных позициях после разворота не более одного подмассива (последовательного отрезка) $$$a$$$.

Пример
Входные данные
4
8
1 7 3 4 7 6 2 9
5
1 2 1 2 1
10
7 8 4 5 7 6 8 9 7 3
4
3 1 2 1
Выходные данные
26
5
37
5