Мальчик Петя и его друг, 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\) удалением нескольких (возможно, ни одного или всех) элементов.
Примечание
В первом тестовом примере последовательность операций выглядит так: \(\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\).
В четвертом тестовом примере достаточно выбрать всю последовательность в качестве подпоследовательности, а затем отнять единицу от северных чисел и прибавить единицу к южным. Таким образом, последовательность занулится за одну операцию.
В пятом тестовом примере не нужно делать никаких операций, поскольку последовательность уже и так состоит из нулей.