Задача H. Монотонность ≡

Условие

Мальчику Мише подарили колоду, содержащую n карт. На каждой карте записано некоторое натуральное число a_i. После перетасовки их, он разложил карты на столе в линию.

Он решил, что линия карт является монотонной, если существует такое i, выбрав которое все карты от 1 до i являются одной четностью, а от i + 1 до n другой. При этом допускается ситуация, когда на столе только одна четность. Например, линии из карт [2, 4, 3, 1, 5]; [3, 9, 13, 21, 4]; [2, 4, 6, 8, 10] являются монотонными, а линия [2, 3, 4, 5, 6] нет.

Он хочет убрать несколько (возможно, ноль) карт со стола, чтобы линия стала монотонной. Но он хочет оставить максимально длинную линию, поэтому он уберет минимальное количество карт. Сам Миша хоть и любит карты, но не любит ничего вычислять, поэтому он просит Вас написать программу, которая рассчитает, какое минимальное количество карт ему надо убрать со стола, чтобы получилась монотонная последовательность.

Формат входных данных

В первой строке задано натуральное число n — количество карт в колоде.

В следующей строке записано n натуральных чисел a_i — последовательно расположенные карты на столе.

Формат выходных данных

Выведите одно целое число — минимальное количество карт, которое необходимо убрать из колоды.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ a_i ≤ 10⁹

Пояснение к примеру

В первом примере мы можем убрать число 2, тем самым сделаем слева [4], а справа [3, 5, 9]

Во втором примере мы можем убрать числа 7 и 8, тем самым сделаем слева [4, 6, 2], а справа [5, 3]

Примеры тестов

5
4 3 5 2 9

1

7
4 7 6 2 5 8 3

2

6
2 4 6 8 10 14

0