[Solution] Qpwoeirut And The City Codeforces Solution

C. Qpwoeirut And The City

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Qpwoeirut has taken up architecture and ambitiously decided to remodel his city.

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

Building i$i$ is cool if it is taller than both building i−1$i-1$ and building i+1$i+1$ (and both of them exist). Note that neither the 1$1$-st nor the n$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.

Solution Click Below:-  👉CLICK HERE

 Find the minimum number of floors Qpwoeirut needs to build in order to maximize the number of cool buildings.

Input

The first line contains a single integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases.

The first line of each test case contains the single integer n$n$ (3≤n≤105$3\le n\le {10}^5$) — the number of buildings in

Another String Minimization Problem Codeforces Solution

Making Towers Codeforces Solution

Qpwoeirut And The City Codeforces Solution

Chopping Carrots (Easy Version) Codeforces Solution

Chopping Carrots (Hard Version) Codeforces Solution

 Qpwoeirut's city.

The second line of each test case contains n$n$ integers h1,h2,…,hn$h_1,h_2,\dots ,h_n$ (1≤hi≤109$1\le h_i\le {10}^9$) — the number of floors in each of the buildings of the city.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

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.