时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
There are n columns of blocks standing in a row. The i-th column has 
blocks in the beginning. Each block has size 
. Define (x,y) represent the block at column x and is the y-th block from bottom to top. You can perform one operation:
- Push one block to the left, that means you choose one block which has no block at its right and make it move to the left. Because of the friction, the block above it will also move to the left, and because the blocks cannot intersect, the block at its left will move to the left either. This will cause a chain reaction. After every block moved, if some blocks hang in the air, then it will fall because of gravitation. Note that the blocks at column 1 can't move to the left, so if a movement will cause a block at column 1 move, you can't perform this operation.
- Push one block to the left, that means you choose one block which has no block at its right and make it move to the left. Because of the friction, the block above it will also move to the left, and because the blocks cannot intersect, the block at its left will move to the left either. This will cause a chain reaction. After every block moved, if some blocks hang in the air, then it will fall because of gravitation. Note that the blocks at column 1 can't move to the left, so if a movement will cause a block at column 1 move, you can't perform this operation.
Formally, let 
be the number of blocks in the i-th column now, then you can choose block (x,y) that satisfy 
and 
(or x=n ). let l be the greatest position that satisfies 
and 
, then you can perform this operation as long as l exists. Then for all blocks (i,j) that satisfy 
and 
, it moves to (i-1,j). After that, for blocks (x,y) (y>1) that there are no blocks in (x,y-1), it moves to (x,y-1). Repeat doing it until no blocks satisfy the condition.
This shows an operation that pushes the block at (6,4), and the value of l is 3.
The goal of the game is to minimize the height of blocks. You need to operate any times of the operation and minimize
, where represents the number of blocks in the end. Output the minimize value.
The goal of the game is to minimize the height of blocks. You need to operate any times of the operation and minimize
输入描述:
The first line contains one integer T— the number of test cases.
The first line of each test case contains only one integer— the number of columns of blocks in the game.
The second line of each test case contains n integers— the number of blocks in each column at the beginning.
The sum of n over all test cases does not exceed.
输出描述:
Print T integers — for each test case output the minimum value of