codeforces#P1990D. Grid Puzzle

Grid Puzzle

Description

You are given an array $a$ of size $n$.

There is an $n \times n$ grid. In the $i$-th row, the first $a_i$ cells are black and the other cells are white. In other words, note $(i,j)$ as the cell in the $i$-th row and $j$-th column, cells $(i,1), (i,2), \ldots, (i,a_i)$ are black, and cells $(i,a_i+1), \ldots, (i,n)$ are white.

You can do the following operations any number of times in any order:

  • Dye a $2 \times 2$ subgrid white;
  • Dye a whole row white. Note you can not dye a whole column white.

Find the minimum number of operations to dye all cells white.

The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

For each test case:

  • The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the size of the array $a$.
  • The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq n$).

It's guaranteed that the sum of $n$ over all test cases will not exceed $2 \cdot 10^5$.

For each test case, output a single integer — the minimum number of operations to dye all cells white.

Input

The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

For each test case:

  • The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the size of the array $a$.
  • The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq n$).

It's guaranteed that the sum of $n$ over all test cases will not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of operations to dye all cells white.

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

Note

In the first test case, you don't need to do any operation.

In the second test case, you can do:

  • Dye $(1,1), (1,2), (2,1)$, and $(2,2)$ white;
  • Dye $(2,3), (2,4), (3,3)$, and $(3,4)$ white;
  • Dye $(3,1), (3,2), (4,1)$, and $(4,2)$ white.

It can be proven $3$ is the minimum number of operations.

In the third test case, you can do:

  • Dye the first row white;
  • Dye $(2,1), (2,2), (3,1)$, and $(3,2)$ white.

It can be proven $2$ is the minimum number of operations.