B. Make it Zigzagtime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAn arbitrary array of integers $$$b$$$ of length $$$m$$$ is considered awesome if for all $$$i$$$ ($$$1 \le i < m$$$): if $$$i$$$ is odd then $$$b_i < b_{i + 1}$$$ holds. if $$$i$$$ is even then $$$b_i > b_{i + 1}$$$ holds. In other words, the following inequality is true: $$$b_1 < b_2 > b_3 < b_4 \ldots$$$You are given an array of positive integers $$$a$$$ of length $$$n$$$. You may do either of the following operations any number of times, in any order: operation $$$1$$$: select an integer $$$i$$$ ($$$1 \le i \le n$$$) and do: $$$a_i := \max(a_1,\ldots,a_i)$$$, that is, replace $$$a_i$$$ with the prefix max up to $$$i$$$. operation $$$2$$$: select an integer $$$i$$$ ($$$1 \le i \le n$$$) and then decrease $$$a_i$$$ by $$$1$$$. Determine the minimum number of times you need to do operation $$$2$$$ to make $$$a$$$ awesome. Note that you do not need to minimise the number of times you perform operation $$$1$$$.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.OutputFor each testcase, output the minimum cost to make $$$a$$$ awesome.ExampleInput751 4 2 5 343 3 2 156 6 6 6 671 2 3 4 5 6 733 2 121 2965 85 19 53 21 79 92 29 96Output01361013NoteIn the first test case, the array is already awesome so no operations need to be done.In the second test case, $$$a$$$ can be made awesome as follows: use operation $$$2$$$ and decrease $$$a_1$$$ by $$$1$$$. $$$[\color{red}3, 3, 2, 1] \rightarrow [\color{red}2, 3, 2, 1]$$$. use operation $$$1$$$ and change $$$a_4$$$ to $$$\max(2, 3, 2, 1) = 3$$$. $$$[2, 3, 2, \color{red}1] \rightarrow [2, 3, 2, \color{red}3]$$$. $$$[2, 3, 2, 3]$$$ is awesome as $$$2 < 3 > 2 < 3$$$. It can be proven that this is the minimum number of times operation $$$2$$$ needs to be performed.