platinum_Shock_Wave (USACO January_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: number theory, greedy, convex hull, binary search

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.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $T$ ($1 \leq T \leq 100$) representing the number of
test cases.
Line $2t$ contains a single integer $N$, the number of tiles in test case $t$.
Line $2t+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$.
OUTPUT FORMAT (print output to the terminal / stdout):
$T$ lines, the $i$th line representing the answer to the $i$th test case.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
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.
SCORING:
Input 2: All $p_i$ are equal.
Inputs 3-6: $N\le 100$
Inputs 7-14: No additional constraints.
Problem credits: Suhas Nagar

Starter code:

Grader code:

Setup script:

Evaluation script: