# [Solution] Qpwoeirut And The City solution codeforces

Qpwoeirut And The City solution codeforces – Qpwoeirut has taken up architecture and ambitiously decided to remodel his city.

## [Solution] Qpwoeirut And The City solution codeforces

Qpwoeirut’s city can be described as a row of 𝑛n buildings, the 𝑖i-th (1𝑖𝑛1≤i≤n) of which is 𝑖hi floors high. You can assume that the height of every floor in this problem is equal. Therefore, building 𝑖i is taller than the building 𝑗j if and only if the number of floors 𝑖hi in building 𝑖i is larger than the number of floors 𝑗hj in building 𝑗j.

Building 𝑖i is cool if it is taller than both building 𝑖1i−1 and building 𝑖+1i+1 (and both of them exist). Note that neither the 11-st nor the 𝑛n-th building can be cool.

To remodel the city, Qpwoeirut needs to maximize the number of cool buildings. To do this, Qpwoeirut can build additional floors on top of any of the buildings to make them taller. Note that he cannot remove already existing floors.

Since building new floors is expensive, Qpwoeirut wants to minimize the number of floors he builds. Find the minimum number of floors Qpwoeirut needs to build in order to maximize the number of cool buildings.

## [Solution] Qpwoeirut And The City solution codeforces

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

The first line of each test case contains the single integer 𝑛n (3𝑛1053≤n≤105) — the number of buildings in Qpwoeirut’s city.

The second line of each test case contains 𝑛n integers 1,2,,𝑛h1,h2,…,hn (1𝑖1091≤hi≤109) — the number of floors in each of the buildings of the city.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.

Output

For each test case, print a single integer — the minimum number of additional floors Qpwoeirut needs to build in order to maximize the number of cool buildings.

Example
input

Copy
6
3
2 1 2
5
1 2 1 4 3
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1
6
1 10 1 1 10 1
8
1 10 11 1 10 11 10 1


## [Solution] Qpwoeirut And The City solution codeforces

output

Copy
2
0
3
3
0
4

Note

In the first test case, it is optimal for Qpwoeirut to make the second building cool by building 22 additional floors on top of it, making it taller than both of its adjacent buildings. The final heights of buildings will be [2,3⎯⎯,2][2,3_,2].

In the second test case, the number of cool buildings is already maximized, so Qpwoeirut does not need to do anything.

In the third test case, it is optimal for Qpwoeirut to make the third and fifth buildings cool by building 22 additional floors onto the third building and 11 additional floor onto the fifth building. The final heights of buildings will be [3,1,6⎯⎯,5,6⎯⎯,2][3,1,6_,5,6_,2].

## [Solution] Qpwoeirut And The City solution codeforces

It can be shown that it is impossible to make more than 22 of the buildings cool, or to make 22 buildings cool using fewer than 33 additional floors.

In the fourth test case, Qpwoeirut can either make the second building cool, or he can make the third building cool. Either way, he will be building 33 additional floors and maximizing the number of cool buildings. The final heights of buildings will be [4,2,4⎯⎯,3,5,3,6,1][4,2,4_,3,5,3,6,1] or [4,5⎯⎯,1,3,5,3,6,1][4,5_,1,3,5,3,6,1].