L. Shrimpinous
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The sunken city of Aqua Badran is the jewel of the deep. Once a prosperous kingdom on the surface, it was swallowed by the sea in an age beyond memory yet far from being lost, it grew into one of the great underwater civilizations: a glittering metropolis of coral towers, pearl-paved boulevards, and bustling reef markets. Travelers from every trench come to taste its food, and at the heart of the city stands its most celebrated landmark, the legendary deep-sea restaurant Shrimpinous. Once a year, Shrimpinous hosts the prestigious Al3afawiah Festival, judged by the legendary merfolk chef Al3afawiah himself.

Along a long underwater reef, $$$n$$$ chefs have set up their cooking stations in a single row. The $$$i$$$-th chef ($$$1 \le i \le n$$$) has prepared a signature shrimp dish with flavor intensity $$$h_i$$$ (measured on the official Shrimpinous Spice Scale).

Al3afawiah declares a chef's dish legendary if and only if its flavor intensity is strictly greater than the flavors of both the chef to their left and the chef to their right. By this rule, the first and last chefs on the reef can never have legendary dishes, since they don't have neighbors on both sides.

The chefs want to maximize the number of legendary dishes so that Aqua Badran's culinary reputation echoes through the trenches. To boost a dish, a chef can sprinkle pinches of secret abyssal seasoning onto it — each pinch increases that dish's flavor by exactly $$$1$$$. A chef can add any non-negative number of pinches, but flavor cannot be removed.

Since the seasoning is rare and harvested from glowing kelp in the deep trenches, the chefs want to use as few pinches as possible while still maximizing the number of legendary dishes.

Find the minimum total number of pinches needed.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of competition rounds.

For each round:

  • The first line contains an integer $$$n$$$ ($$$3 \le n \le 10^5$$$) — the number of chefs on the reef.
  • The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — the initial flavor intensities.
The sum of $$$n$$$ over all rounds does not exceed $$$2 \cdot 10^5$$$.
Output

For each round, print a single integer — the minimum number of pinches the chefs must add so that the number of legendary dishes judged by Al3afawiah is maximized.

Example
Input
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
Output
2
0
3
3
0
4
Note

In the first round, adding $$$2$$$ pinches to chef $$$2$$$ gives flavors $$$[2, \underline{3}, 2]$$$ — one legendary dish.

In the second round, chefs $$$2$$$ and $$$4$$$ are already legendary, so no seasoning is needed.

In the third round, adding $$$2$$$ pinches to chef $$$3$$$ and $$$1$$$ pinch to chef $$$5$$$ gives $$$[3, 1, \underline{6}, 5, \underline{6}, 2]$$$ — two legendary dishes using $$$3$$$ pinches, the minimum possible.

In the fourth round, the chefs can make either chef $$$2$$$ or chef $$$3$$$ legendary along with chefs further down the reef. Either way, exactly $$$3$$$ pinches are needed.