D. Stamina
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Templates for this problem are available here.

Alice is standing at position $$$1$$$ of a straight road and wants to reach position $$$n$$$. Initially, she has $$$0$$$ stamina. On each day, she can do exactly one of the following:

  • Walk forward from position $$$i$$$ to position $$$i + 1$$$ and lose $$$1$$$ stamina. She can only do this if she has at least $$$1$$$ stamina.
  • Rest at her current position $$$i$$$ and gain $$$a_i$$$ stamina.
What is the minimum number of days Alice needs to reach position $$$n$$$?
Input

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 number of positions on the road.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the amount of stamina Alice gains by resting at position $$$i$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one integer — the minimum number of days Alice needs to reach position $$$n$$$.

Example
Input
3
4
1 1 1 1
4
1 2 3 4
5
3 1 3 1 3
Output
6
5
6
Note

In the first test case, Alice can rest at position $$$1$$$ for the first $$$3$$$ days and walk forward for the next $$$3$$$ days.

In the second test case, Alice can do the following:

  1. Rest at position $$$1$$$. After this, her stamina is $$$1$$$.
  2. Walk to position $$$2$$$. After this, her stamina is $$$0$$$.
  3. Rest at position $$$2$$$. After this, her stamina is $$$2$$$.
  4. Walk to position $$$3$$$. After this, her stamina is $$$1$$$.
  5. Walk to position $$$4$$$. After this, her stamina is $$$0$$$.