SACITY - Sadde and His City


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 Hmini) and number of buildings having greater height in right of that building(say Hmaxi). He put Hmini + Hmaxi number of flags in container of ith 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 Hi denoting height of each building.

Constraints

T<=10

0 < N <= 105

0 <= Hi <= 109

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

hide comments
Thotsaphon Thanatipanonda: 2016-02-10 10:07:38

Flags in one container can be distributed to many buildings. But in one building can get flags from one container.

.:frUstrAteD:.: 2015-03-06 12:33:54

@Nishant can you please have a look at my last submission Why i am getting WA ? Am i doing the right thing ?

Last edit: 2015-03-06 19:20:41
NISHANT RAJ: 2014-12-18 18:12:11

@[themighty] deathsurgeon in question I have written every building should get same amount of flag .

[themighty] deathsurgeon: 2014-12-18 16:29:24

@Nishant Thank you! One more thing though. In second test case, the respective flags are {1,2,2,1,0}. A total of 6. How are these 6 being distributed among 5 buildings? Even if they are unevenly distributed, shouldn't the maximum be 2? Since, atleast one of them will get atleast 2 flags.

NISHANT RAJ: 2014-12-18 15:43:21

@[themighty] deathsurgeon Existing flags are being distributed(Flags you put in container on basis of their heights) . You are suppose to find maximum number of flag all building can get .

[themighty] deathsurgeon: 2014-12-18 08:23:27

I din't understand the 4th paragraph of this question.
He takes all the containers from this city, which had flags in them, shuffles them (the containers). "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." Are the existing flags being distributed? Or additional flags are being given? And what are we supposed to find? Can someone please explain the second sample test case?


Added by:NISHANT RAJ
Date:2014-11-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64