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

Массив называется хорошим, если для каждого подмассива$$$^{\text{∗}}$$$ длиной не менее $$$2$$$ сумма элементов на четных индексах (в индексации оригинального массива) больше или равна сумме элементов на нечетных индексах. Массив нумеруется с $$$1$$$.

Например, массивы $$$[3,8,4,4]$$$ и $$$[2,3,1,4,2]$$$ являются хорошими. Массив $$$[0,2,4,1]$$$ не является хорошим, потому что в подмассиве $$$[2,4,1]$$$ элементы на четных индексах в оригинальном массиве равны $$$2$$$ (индекс $$$2$$$) и $$$1$$$ (индекс $$$4$$$), в то время как единственным элементом на нечетном индексе является $$$4$$$ (индекс $$$3$$$). Поскольку $$$2 + 1 \lt 4$$$, условие не выполняется для этого подмассива.

Вам дан массив из $$$n$$$ целых неотрицательных чисел $$$a_1,a_2,\ldots,a_n$$$. За одну операцию вы можете уменьшить любое значение в массиве на $$$1$$$, но все элементы должны оставаться неотрицательными. Ваша задача — найти минимальное количество операций, необходимое для того, чтобы сделать массив $$$a$$$ хорошим. Можно доказать, что возможно сделать массив хорошим, используя конечное количество операций.

$$$^{\text{∗}}$$$Массив $$$b$$$ является подмассивом массива $$$a$$$, если $$$b$$$ может быть получен из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

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

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

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

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

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

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

Пример
Входные данные
8
4
3 8 4 4
4
0 2 3 5
2
3 1
5
2 3 1 4 2
4
0 2 4 1
5
3 1 4 5 1
11
3 0 5 4 4 5 3 0 3 4 1
12
410748345 10753674 975233308 193331255 893457280 279719251 704970985 412553354 801228787 44181004 1000000000 3829103
Выходные данные
0
1
2
0
3
6
14
4450984776
Примечание

В первом наборе входных данных массив $$$a$$$ уже хороший, поэтому ответ равен $$$0$$$. Ниже приведены проверки для каждого подмассива:

ПодмассивСумма четных индексовСумма нечетных индексовУсловие выполнено?
$$$[3,8]$$$$$$8$$$$$$3$$$Да
$$$[8,4]$$$$$$8$$$$$$4$$$Да
$$$[4,4]$$$$$$4$$$$$$4$$$Да
$$$[3,8,4]$$$$$$8$$$$$$3+4=7$$$Да
$$$[8,4,4]$$$$$$8+4 = 12$$$$$$4$$$Да
$$$[3,8,4,4]$$$$$$8+4=12$$$$$$3 + 4 = 7$$$Да

Во втором наборе входных данных массив $$$a$$$ не является хорошим:

ПодмассивСумма четных индексовСумма нечетных индексовУсловие выполнено?
$$$[0,2]$$$$$$2$$$$$$0$$$Да
$$$[2,3]$$$$$$2$$$$$$3$$$Нет
$$$[3,5]$$$$$$5$$$$$$3$$$Да
$$$[0,2,3]$$$$$$2$$$$$$0+3=3$$$Нет
$$$[2,3,5]$$$$$$2 + 5 = 7$$$$$$3$$$Да
$$$[0,2,3,5]$$$$$$2+5 = 7$$$$$$0+3 = 3$$$Да

Однако, если мы выполним операцию на индексе $$$3$$$, массив станет $$$[0,2,2,5]$$$ и теперь он хороший:

ПодмассивСумма четных индексовСумма нечетных индексовУсловие выполнено?
$$$[0,2]$$$$$$2$$$$$$0$$$Да
$$$[2,2]$$$$$$2$$$$$$2$$$Да
$$$[2,5]$$$$$$5$$$$$$2$$$Да
$$$[0,2,2]$$$$$$2$$$$$$0+2=2$$$Да
$$$[2,2,5]$$$$$$2 + 5 = 7$$$$$$2$$$Да
$$$[0,2,2,5]$$$$$$2+5 = 7$$$$$$0+2 = 2$$$Да

Таким образом, ответ равен $$$1$$$.