Sadde owns a country named as Sadde land. In Sadde land each city consists of only one row of building.

Sadde being the king wanted to know the score of cities in his country. Sadde gives the task of scoring to one of his minister Dukker.

Each city consists of “N” buildings in a single row and each building is having a container in front of them. For each building in the city Dukker calculate the number of buildings having less height in left of that building(say Hmin_i) and number of buildings having greater height in right of that building(say Hmax_i). He put Hmin_i + Hmax_i number of flags in container of i^th building.

He took all containers from the buildings and shuffles them. Now he wants to distribute flags among buildings of city such that each building should get same number of flag and a building will get all the flags from single container.

Score of city is the maximum number of flags that a building can have.

Input

Input consist of T number of test cases. Each case contains two lines. First line contains N denoting number of buildings in a city. Second line will contain N integers H_i denoting height of each building.

Constraints

T<=10

0 < N <= 10⁵

0 <= H_i <= 10⁹

Output

Output should contain T line denoting score of that city.

Example

Input:
3
5
1 2 3 4 5
5
4 2 5 3 1
3
3 3 3

Output:
4
1
0