5204：不随机的法术

又在炉石传说中，有一个职业叫做法师，他有这样一张牌，可以对敌方随从打出这一张牌

你是一个优秀的牌手，但是！这张卡是随机对敌方随从造成伤害，优秀的牌手都很不喜欢有如此强随机性的卡牌，那么现在，我们修改这张卡的效果，以下是修改后的描述：

星辰能量：法术会击中敌方随从$$n$$次，每次只击中一个敌方随从，每个敌方随从恰好被击中一次，假设你使用星辰能量选择初始目标是$$i$$，星辰能量之后将随机选择一个敌方随从，该敌方随从未被法术击中，并且与其中一个已被击中过的敌方随从相邻。被法术击中的第一个敌方随从受到 $$x$$伤害，第二个敌方随从受到 $$(x−1)$$伤害，第三个受到 $$(x−2)$$伤害，以此类推...

优秀的牌手总是可以使用一个星辰能量法术消灭所有的敌方随从，所以你需要选择一个初始目标并且计算出杀死所有敌方随从所需的最小初始法术伤害$$x$$。注意，你只能选择最初的目标$$i$$和初始法术的伤害$$x$$，法术之后选择哪一个敌方随从应该被认为是随机的。

你只能使用一次星辰能量消灭所有敌方随从，敌方随从被认为死亡当它受到的伤害不小于其血量。你需要计算出最小的法术初始伤害$$x$$，使得无论在每一次击中哪个符合条件的敌方随从，都能消灭所有敌方随从。

第一行是一个整数 $$T( 1 ≤ T ≤ 1e4 )$$代表案例组数。

对于每组案例，

第一行输入一个整数$$n(1  ≤ n  ≤ 1e5)$$，代表有$$n$$个敌方随从。

第二行输入包含$$n$$个整数，$$a_1,a_2,a_3,.....a_n( 1≤a_i≤1e9 )$$表示第$$a_i$$个敌方随从的血量。

保证所有测试用例中 $$n$$ 的总和不超过 $$1e6$$。

针对每组样例，输出一个整数，即是消灭所有敌方随从所需的最小的初始法术伤害，并且法术命中的顺序可以是给定规则内的任何可能，然后换行。

3

6

2 1 5 6 4 3

5

4 4 4 4 4

2

1 1000000000

8

8

1000000000

对于第二组样例，我们选择初始法术伤害为$$8$$，初始目标为第五个敌方随从，那么，

第一次受到伤害的是第五个敌方随从，造成$$8$$点伤害，造成伤害后敌方随从的血量如下$$[4,4,4,4,0]$$，

第二次受到伤害的只能是第四个敌方随从，造成$$7$$点伤害，造成伤害后敌方随从的血量如下$$[4,4,4,0,0]$$，

第三次受到伤害的只能是第三个敌方随从，造成$$6$$点伤害，造成伤害后敌方随从的血量如下$$[4,4,0,0,0]$$，

第四次受到伤害的只能是第二个敌方随从，造成$$5$$点伤害，造成伤害后敌方随从的血量如下$$[4,0,0,0,0]$$，

第五次受到伤害的只能是第一个敌方随从，造成$$4$$点伤害，造成伤害后敌方随从的血量如下$$[0,0,0,0,0]$$，

至此已经消灭所有的敌方随从。

TKK寒假赛Round#17