Задача по информатике

D. Пила
Ограничение времени 1 секунда
Ограничение памяти 256 Мб
Ввод стандартный ввод
Вывод стандартный вывод
Последовательность чисел
a
1
a
1
​
,
a
2
a
2
​
, …,
a
n
a
n
​
назовем пилообразной, если в ней знаки разностей двух соседних чисел чередуются. А именно:

a
i
a
i
​
>
a
i
+
1
a
i+1
​
для любого нечетного
i
<
n
i<n;
a
i
a
i
​
<
a
i
+
1
a
i+1
​
для любого четного
i
<
n
i<n;
В частности, последовательность из одного числа всегда является пилообразной.

Последовательность назовем почти пилообразной, если в ней можно переставить числа таким образом, чтобы она стала пилообразной.

Вам дана последовательность
b
1
b
1
​
,
b
2
b
2
​
, …,
b
n
b
n
​
. Посчитайте, какое наименьшее количество чисел в ней нужно изменить, чтобы она стала почти пилообразной.

Формат ввода
Первая строка содержит целое число
n
n (
2
≤
n
≤
2
⋅
1
0
5
2≤n≤2⋅10
5
,
n
n — четное) — количество чисел в последовательности.

Вторая строка содержит
n
n целых чисел
b
i
b
i
​
(
1
≤
b
i
≤
1
0
9
1≤b
i
​
≤10
9
).

Формат вывода
Выведите одно число — наименьшее количество изменений.

Система оценивания
Группа Баллы Доп. ограничения Система оценки
0
0
0
0 — Тесты из условия
1
1
30
30
n
≤
16
n≤16 Полная группа
2
2
40
40
n
≤
2000
n≤2000 Полная группа
3
3
30
30 — Полная группа
Пример 1
Ввод Вывод
4
2 2 4 2
1
Пример 2
Ввод Вывод
4
4 3 2 1
0
Примечания
В первом примере достаточно поменять первое число с
2
2 на
3
3. Тогда можно будет составить, например, последовательность
(
4
,
2
,
3
,
2
)
(4,2,3,2).

Во втором примере из исходных чисел можно составить, например, последовательность
(
4
,
1
,
3
,
2
)
(4,1,3,2).