Shock Wave

문제

Bessie is experimenting with a powerful hoof implant that has the ability to create massive shock waves. She has $NN$ ($2\le N\le {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 10^5$) tiles lined up in front of her, which require powers of at least $p_0,p_1,\dots ,p_{N-1}p\_0,p\_1,\backslash dots,p\_\{N-1\}$ to break, respectively ($0\le p_i\le {10}^{18}0\; \backslash leq\; p\_i\; \backslash leq\; 10^\{18\}$).

Bessie can apply power by punching a specific tile but due to the strange nature of her implant, it will not apply any power to the tile she punches. Instead, if she chooses to punch tile $xx$ once, where $xx$ is an integer in $[0,N-1][0,N-1]$, it applies $\mathrm{\mid }i-x\mathrm{\mid }|i-x|$ power to tile $ii$ for all integers $ii$ in the range $[0,N-1][0,N-1]$. This power is also cumulative, so applying $22$ power twice to a tile will apply a total of $44$ power to the tile.

Please determine the fewest number of punches required to break all the tiles.

입력

The first line contains $TT$ ($1\le T\le 1001\; \backslash leq\; T\; \backslash leq\; 100$) representing the number of test cases.

Line $2t2t$ contains a single integer $NN$, the number of tiles in test case $tt$.

Line $2t+12t+1$ contains $NN$ space separated numbers $p_0,p_1,\dots ,p_{N-1}p\_0,p\_1,\; \backslash ldots,\; p\_\{N-1\}$ representing that tile $ii$ takes $p_{i}p\_i$ power to be broken.

It is guaranteed that the sum of all $NN$ in a single input does not exceed $5\cdot {10}^{5}5\backslash cdot\; 10^5$.

출력

$TT$ lines, the $ii$th line representing the answer to the $ii$th test case.

6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000

2
3
2
4
4
2000000000000000000