Дан массив из \(n\) целых чисел, каждое из которых — \(0\), \(1\) или \(2\). Изначально каждый элемент массива покрашен в синий цвет.
Ваша цель — покрасить все элементы в красный цвет. Для этого вы можете выполнять операции двух типов:
- заплатить одну монету, выбрать синий элемент и покрасить его в красный цвет;
- выбрать красный элемент, не равный \(0\), и соседний с ним синий элемент, уменьшить выбранный красный элемент на \(1\), а выбранный синий элемент покрасить в красный цвет.
Какое минимальное количество монет вам придется потратить, чтобы покрасить все элементы в красный?
Выходные данные
Выведите одно целое число — минимальное количество монет, которое вам придется потратить, чтобы покрасить все элементы массива в красный цвет.
Примечание
В первом примере из условия можно покрасить все элементы в красный за одну монету следующим образом:
- покрасить \(2\)-й элемент в красный за одну монету;
- уменьшить \(2\)-й элемент на \(1\) и покрасить \(1\)-й элемент в красный;
- уменьшить \(2\)-й элемент на \(1\) и покрасить \(3\)-й элемент в красный.
Во втором примере из условия можно покрасить все элементы в красный за две монеты следующим образом:
- покрасить \(4\)-й элемент в красный за одну монету;
- уменьшить \(4\)-й элемент на \(1\) и покрасить \(3\)-й элемент в красный;
- покрасить \(1\)-й элемент в красный за одну монету;
- уменьшить \(3\)-й элемент на \(1\) и покрасить \(2\)-й элемент в красный.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 2 0
|
1
|
|
2
|
4
0 0 1 1
|
2
|
|
3
|
7
0 1 0 0 1 0 2
|
4
|