Bob, the builder, has received a large construction assignment. He has received the preferred construction plan for constructing the buildings. The construction plan consists of the positions and heights of the buildings to be constructed. But Bob finds some problems in the given plan. He thinks that there will be clogging of rain water during the monsoons. So he wanted to enhance the plan such that there is no water clogging in between the buildings during monsoon.
Water will be collected above a building if there are buildings of strictly greater height than it on both sides. You can consider there are buildings of height zero before the first building and after the last building.
But shifting the buildings from its original position in the plan will incur a particular cost. The cost incurred will be the absolute difference between the index positions of the new position and the old position.
All the heights of the buildings are distinct. Help Bob come up with a plan to satisfy the conditions with minimum cost.
Safe Plan means either the buildings are in ascending or descending.
Input
First line contains T, the number of test cases.
First line of each test case contains n, the number of buildings in the given construction plan. Next line contains n space separated integers, denoting the height of building at position i.
Output
Output n lines, each line containing the answer to the corresponding test case.
Constraints
1≤T≤100
0≤n≤105
0≤hi≤109
One construction plan may be 1 2 3 4 5. This will give us a cost of 2.
Since Building at index 1 will be moved to index 2 => cost = 1
Building at index 2 will be shifted to index 1 => cost = 1
Total cost = 2.
