#OJ1558. Time Limit: 3 Sec  Memory Limit: 256 MB

Time Limit: 3 Sec  Memory Limit: 256 MB

Time Limit: 3 Sec  Memory Limit: 256 MB

Description

有N个小朋友排成一排,每个小朋友有一个得分,现在你要将一些糖果分给这N个小朋友分配的原则如下: 1 每个小朋友必须至少有一个糖果 2 如果某个小朋友的得分大于他左边的(如果存在)的小朋友的分值,那么他得到的糖果必须大于左边的小朋友的糖果数,   如果某个小朋友的得分大于他右边的(如果存在)的小朋友的分值,那么他得到的糖果必须大于右边的小朋友的糖果数 请问你最少要用多少糖果分给这N个小朋友

Input

第一行为样例组数T(1<=T<=100)      每组样例 第一行输入为N(1<=N<=100000)      第二行N个整数(int范围)sore[1],score[2],score[3]....socreN代班每个小朋友的得分

Output

每组输出一行,代表最少需要的糖果数

Sample Input

3
3
1 1 1
4
1 2 3 4
5
1 2 9 2 1

Sample Output

3
10
9

HINT

Append Code