AT_abc459_f [ABC459F] -1, +1

You are given a sequence of non-negative integers $ A = (A_1, A_2, \ldots, A_N) $ of length $ N $ . You can perform the following operation on $ A $ zero or more times: - Choose an integer $ i $ with $ 1 \le i \le N - 1 $ , decrease $ A_i $ by $ 1 $ , and increase $ A_{i+1} $ by $ 1 $ . Find the minimum number of operations required to make $ A $ strictly increasing. It can be proved that the answer is less than $ 2^{63} $ . You are given $ T $ test cases; solve each.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ The $ i $ -th $ (1 \le i \le T) $ test case $ \text{case}_i $ is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Output the answers for the test cases in order, separated by newlines.

### Sample Explanation 1 Consider the first test case. By performing the following operations, $ A $ can be made strictly increasing in three operations: - Choose $ i=1 $ . $ A $ becomes $ (-1, 2, 0) $ . - Choose $ i=2 $ . $ A $ becomes $ (-1, 1, 1) $ . - Choose $ i=2 $ . $ A $ becomes $ (-1, 0, 2) $ . It is impossible to make $ A $ strictly increasing in fewer than three operations, so output $ 3 $ . ### Constraints - $ 1 \le T \le 3 \times 10^5 $ - $ 1 \le N \le 2 \times 10^5 $ - $ 0 \le A_i \le 10^9 $ - The sum of $ N $ across all test cases is at most $ 6 \times 10^5 $ . - All input values are integers.