| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 7 | 5 | 5 | 71.429% |
Bessie is experimenting with a powerful hoof implant that has the ability to create massive shock waves. She has $N$ (2ドル \leq N \leq 10^5$) tiles lined up in front of her, which require powers of at least $p_0,p_1,\dots,p_{N-1}$ to break, respectively (0ドル \leq p_i \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 $x$ once, where $x$ is an integer in $[0,N-1],ドル it applies $|i-x|$ power to tile $i$ for all integers $i$ in the range $[0,N-1]$. This power is also cumulative, so applying 2ドル$ power twice to a tile will apply a total of 4ドル$ power to the tile.
Please determine the fewest number of punches required to break all the tiles.
The first line contains $T$ (1ドル \leq T \leq 100$) representing the number of test cases.
Line 2ドルt$ contains a single integer $N,ドル the number of tiles in test case $t$.
Line 2ドルt+1$ contains $N$ space separated numbers $p_0,p_1, \ldots, p_{N-1}$ representing that tile $i$ takes $p_i$ power to be broken.
It is guaranteed that the sum of all $N$ in a single input does not exceed 5ドル\cdot 10^5$.
$T$ lines, the $i$th line representing the answer to the $i$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
For the first test, the only way for Bessie to break all the tiles with two punches is to punch 0ドル$ twice, applying total powers of $[0,2,4,6,8]$ respectively.
For the second test, one way for Bessie to break all the tiles with three punches is to punch 0ドル,ドル 2ドル,ドル and 4ドル$ one time each, applying total powers of $[6,5,4,5,6]$ respectively.
For the third test, one way for Bessie to break all the tiles with two punches is to punch 0ドル$ and 1ドル$ one time each, applying total powers of $[1,1,3,5,7]$ respectively.