D. Покраска массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив из $$$n$$$ целых чисел, каждое из которых — $$$0$$$, $$$1$$$ или $$$2$$$. Изначально каждый элемент массива покрашен в синий цвет.

Ваша цель — покрасить все элементы в красный цвет. Для этого вы можете выполнять операции двух типов:

  • заплатить одну монету, выбрать синий элемент и покрасить его в красный цвет;
  • выбрать красный элемент, не равный $$$0$$$, и соседний с ним синий элемент, уменьшить выбранный красный элемент на $$$1$$$, а выбранный синий элемент покрасить в красный цвет.

Какое минимальное количество монет вам придется потратить, чтобы покрасить все элементы в красный?

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

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2$$$).

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

Выведите одно целое число — минимальное количество монет, которое вам придется потратить, чтобы покрасить все элементы массива в красный цвет.

Примеры
Входные данные
3
0 2 0
Выходные данные
1
Входные данные
4
0 0 1 1
Выходные данные
2
Входные данные
7
0 1 0 0 1 0 2
Выходные данные
4
Примечание

В первом примере из условия можно покрасить все элементы в красный за одну монету следующим образом:

  1. покрасить $$$2$$$-й элемент в красный за одну монету;
  2. уменьшить $$$2$$$-й элемент на $$$1$$$ и покрасить $$$1$$$-й элемент в красный;
  3. уменьшить $$$2$$$-й элемент на $$$1$$$ и покрасить $$$3$$$-й элемент в красный.

Во втором примере из условия можно покрасить все элементы в красный за две монеты следующим образом:

  1. покрасить $$$4$$$-й элемент в красный за одну монету;
  2. уменьшить $$$4$$$-й элемент на $$$1$$$ и покрасить $$$3$$$-й элемент в красный;
  3. покрасить $$$1$$$-й элемент в красный за одну монету;
  4. уменьшить $$$3$$$-й элемент на $$$1$$$ и покрасить $$$2$$$-й элемент в красный.