Problem T: Game 始めましょう

Problem T: Game 始めましょう

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 120  Solved: 26
[Submit] [Status] [Web Board] [Creator:]

Description

'Game 始めましょう'是No Game No Life里空常说的一句话,表示游戏开始 
现在我们的游戏也开始吧,假设今天来打比赛的有N名同学,每个同学打完比赛后的积分为a[i],现在某云飞要给你们发一些糖果作为奖励(五一记得提醒某云飞发糖!!!!!),于是让你们围成了一个圈,但是害怕你们其中游戏些人心里不平衡,所以指定了一些规则: 
1.每个人只能看到旁边的人的分数和糖果数。 
2.分数高的人得到的糖果数比分数低的多。 
3.每个人至少一个糖果(参与奖还是要有的) 
现在某云飞想知道最少给你们买多少个糖果才能让你们每个人都开心呢。 

Input

第一行输入一个T,表示测试数据组数(T <= 100) 
每组输入一个正整数N,表示今天参赛的人员个数(N <= 10000) 
接下来输入每个人赛后的积分a[i](0 < a[i] < 100000) 

Output

输出每场比赛某云飞最少需要准备多少个糖果。

Sample Input Copy

2
20
2 2 6 7 7 6 5 4 3 1 3 5 7 9 10 10 12 10 10 10
13
2 3 4 4 5 6 7 6 7 6 5 3 2

Sample Output Copy

55
32