P6563 [SBCOI2020] Always By Your Side

In the blink of an eye, it is spring again... Standing here, I finally realized that my heart has already become connected to that town protected by the Light Jade. ...... “It is spring again...” “Looks like you are ready to stay here.” “Actually, I do not have any big dreams. I am just trying hard to keep things as they are...” “But as long as I can achieve my own dream, what does it matter...” “But right now, I am truly very happy. Just like you said, I have found many joyful things...” “I am also in the same world as you. There is nothing in this world that never changes. So as long as you can find your happiness in other ways, that is enough...” “Yeah, it is time to start a new life......”  “You are really obsessed with this town...” “Because it is full of memories I do not want to forget...”

After returning to this town, her new job is to repair electric wires. Now, one wire is broken. It is known that the wire length is one of $1,2,\cdots,n$. Now, she needs to find out the wire’s length. She can spend $a_i$ money to buy a wire of length $i$. After buying this wire, she can know whether the required wire length is **greater than** $i$. It is guaranteed that $a_1 \le a_2 \le \cdots \le a_n \le 10^9$. Ask what is the minimum amount of money she must spend to guarantee that she can determine the required wire length.

**This problem has multiple test cases**. The first line contains a positive integer $T$, the number of test cases. Then for each test case: one line contains an integer $n$, and the next line contains $n$ integers $a_1,a_2,\cdots,a_n$.

Output $T$ lines, each line containing one answer.

[Sample Explanation] Buy a wire of length $1$, and you can know whether the required length is greater than $1$. Then you can determine whether it is $1$ or $2$, so the answer is $1$. Large sample [link](https://www.luogu.com.cn/paste/csusv11e). [Constraints] This problem uses bundled testdata, with $4$ subtasks in total. $(Subtask 1)(10\%)$, $n \le 15$. $(Subtask 2)(10\%)$, $n \le 500$. $(Subtask 3)(30\%)$, $n \le 2000$. $(Subtask 4)(50\%)$, no additional constraints. For $100\%$ of the testdata, $1 \le n,\sum n \leq 7100,T \leq 500$。$\sum n$ denotes the sum of $n$ over all test cases. Translated by ChatGPT 5