A15656 | $Block Towers$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

There are $n$ block towers, numbered from $1$ to $n$ . The $i$ -th tower consists of $a_i$ blocks. In one move, you can move one block from tower $i$ to tower $j$ , but only if $a_i > a_j$ . That move increases $a_j$ by $1$ and decreases $a_i$ 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?

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of testcases. The first line of each testcase contains a single integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ) — the number of towers. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ) — the number of blocks on each tower. The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$ .

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).

输入 #1

4
3
1 2 3
3
1 2 2
2
1 1000000000
10
3 8 6 7 4 1 2 4 10 1

输出 #1

C++ 编辑器

输入

输出