Дан массив \(a\) размера \(n\).
Есть сетка размером \(n \times n\). В \(i\)-й строке первые \(a_i\) ячеек черные, а остальные ячейки белые. Другими словами, через \((i,j)\) обозначим ячейку в \(i\)-й строке и \(j\)-м столбце, ячейки \((i,1), (i,2), \ldots, (i,a_i)\) черные, а ячейки \((i,a_i+1), \ldots, (i,n)\) белые.
Вы можете выполнять следующие операции любое количество раз в любом порядке:
- Покрасить подсетку размера \(2 \times 2\) в белый цвет;
- Покрасить всю строку в белый цвет. Обратите внимание, что вы не можете покрасить всю колонку в белый цвет.
Найдите минимальное количество операций, которое необходимо, чтобы покрасить все ячейки в белый цвет.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, которое необходимо, чтобы покрасить все ячейки в белый цвет.
Примечание
В первом наборе входных данных вам не нужно выполнять никаких операций.
Во втором наборе входных данных вы можете выполнить следующие операции:
- Покрасить \((1,1), (1,2), (2,1)\) и \((2,2)\) в белый цвет;
- Покрасить \((2,3), (2,4), (3,3)\) и \((3,4)\) в белый цвет;
- Покрасить \((3,1), (3,2), (4,1)\) и \((4,2)\) в белый цвет.
Можно доказать, что минимальное количество операций равно \(3\).
В третьем наборе входных данных вы можете выполнить следующие операции:
- Покрасить первую строку в белый цвет;
- Покрасить \((2,1), (2,2), (3,1)\) и \((3,2)\) в белый цвет.
Можно доказать, что минимальное количество операций равно \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1
0
4
2 4 4 2
4
3 2 1 0
3
0 3 0
3
0 1 3
3
3 1 0
4
3 1 0 3
4
0 2 2 2
6
1 3 4 2 0 4
8
2 2 5 2 3 4 2 4
|
0
3
2
1
2
2
3
2
4
6
|