(MUST SOLVE IN JAVA)

There are n block towers, numbered from 1 to n. The i-th tower consists of ai blocks. In one move, you can move one block from tower i to tower j, but only if ai>aj. That move increases aj by 1 and decreases ai by 1 . You can perform as many moves as you would like (possibly, zero). What's the largest amount of blocks you can have on the tower 1 after the moves? Input The first line contains a single integer t(1t104) - the number of testcases. The first line of each testcase contains a single integer n(2n2105) - the number of towers. The second line contains n integers a1,a2,,an(1ai109) - the number of blocks on each tower. The sum of n over all testcases doesn't exceed 2105. Output For each. testcase, print the largest amount of blocks you can have on the tower 1 after you make any number of moves (possibly, zero). Note In the first testcase, you can move a block from tower 2 10 tower 1 . making the block counts [2,1,3]. Then move a block from tower 3 to tower 1 , making the block counts [3,1,2]. Tower 1 has 3 blocks in it, and you can't obtain a larger amount