CF2154B Make it Zigzag

An 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 $ .

Each 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 $ .

For each testcase, output the minimum cost to make $ a $ awesome.

In 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.