Bessie is experimenting with a powerful hoof implant that has the ability to create massive shock waves. She has N (2≤N≤105) tiles lined up in front of her, which require powers of at least p0,p1,…,pN−1 to break, respectively (0≤pi≤1018).
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≤T≤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 p0,p1,…,pN−1 representing that tile i takes pi power to be broken.
It is guaranteed that the sum of all N in a single input does not exceed 5⋅105.
OUTPUT FORMAT (print output to the terminal / stdout):
T lines, the ith line representing the answer to the ith 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 pi are equal.
Inputs 3-6: N≤100
Inputs 7-14: No additional constraints.
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
