| Codeforces Round 843 (Div. 2) |
|---|
| Закончено |
Мальчик Петя и его друг, Petya++, отправились на BFDMONCON, где сегодня проходит конкурс костюмов.
Проходя по фестивалю, они наткнулись на научный стенд имени профессора Оука и Гольфболла, где им предложили решить интересную задачу.
Дана последовательность из чисел $$$a_1, a_2, \dots, a_n$$$ и вы можете производить несколько операций над этой последовательностью.
Каждая операция должна выглядеть следующим образом. Вы выбираете некоторую подпоследовательность$$$^\dagger$$$. Далее вы называете все числа, находящиеся на нечетных позициях в этой подпоследовательности — северными, а все числа, находящиеся на четных позициях в этой подпоследовательности — южными. При этом учитывается лишь позиция числа в подпоследовательности, а не в исходной последовательности.
Например, рассмотрим последовательность $$$1, 4, 2, 8, 5, 7, 3, 6, 9$$$ и ее подпоследовательность (выделена жирным) $$$1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$$$. Тогда числа $$$4$$$ и $$$5$$$ будут северными, а числа $$$2$$$ и $$$6$$$ — южными.
После этого можно выполнить одно из следующих действий:
- прибавить $$$1$$$ ко всем северным числам и отнять $$$1$$$ от всех южных; или
- прибавить $$$1$$$ ко всем южным числам и отнять $$$1$$$ от всех северных.
Таким образом, из последовательности $$$1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$$$ при выборе описанной выше подпоследовательности можно получить либо $$$1, \mathbf{5}, \mathbf{1}, 8, \mathbf{6}, 7, 3, \mathbf{5}, 9$$$, либо $$$1, \mathbf{3}, \mathbf{3}, 8, \mathbf{4}, 7, 3, \mathbf{7}, 9$$$.
Затем операция заканчивается. Обратите также внимание, что все операции являются независимыми, т. е. по окончании одной операции числа больше не называются северными или южными.
Необходимо с помощью описанных выше операций превратить все числа последовательности в нули. Поскольку до конкурса костюмов осталось совсем немного времени, ребята хотят узнать, какое минимальное количество операций для этого придется совершить.
Увы, ребятам такая задача оказалась не по силам, поэтому они позвали Вас на помощь.
$$$^\dagger$$$ Последовательность $$$c$$$ является подпоследовательностью $$$d$$$, если $$$c$$$ может быть получена из $$$d$$$ удалением нескольких (возможно, ни одного или всех) элементов.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.
Для каждого набора входных данных выведите по одному целому числу в отдельной строке — минимальное количество операций, необходимое, чтобы последовательность состояла только из нулей.
531 2 -351 0 0 -1 -162 -4 3 -5 4 151 -1 1 -1 170 0 0 0 0 0 0
3 2 6 1 0
В первом тестовом примере последовательность операций выглядит так: $$$\mathbf{1}, 2, \mathbf{-3} \longrightarrow 0, \mathbf{2}, \mathbf{-2} \longrightarrow 0, \mathbf{1}, \mathbf{-1} \longrightarrow 0, 0, 0$$$.
Во втором тестовом примере последовательность выглядит так: $$$\mathbf{1}, 0, 0, \mathbf{-1}, -1 \longrightarrow 0, 0, 0, 0, \mathbf{-1} \longrightarrow 0, 0, 0, 0, 0$$$.
В четвертом тестовом примере достаточно выбрать всю последовательность в качестве подпоследовательности, а затем отнять единицу от северных чисел и прибавить единицу к южным. Таким образом, последовательность занулится за одну операцию.
В пятом тестовом примере не нужно делать никаких операций, поскольку последовательность уже и так состоит из нулей.
