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

Дан массив $$$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$$$ в белый цвет;
  • Покрасить всю строку в белый цвет. Обратите внимание, что вы не можете покрасить всю колонку в белый цвет.

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

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Для каждого набора входных данных:

  • Первая строка содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — размер массива $$$a$$$.
  • Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
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
Примечание

В первом наборе входных данных вам не нужно выполнять никаких операций.

Во втором наборе входных данных вы можете выполнить следующие операции:

  • Покрасить $$$(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$$$.