CF2244G.Yura and Deadlines

Yura has $n$ homework assignments. For each assignment, its weight $a_i$ is known — the number of course points Yura will receive if he completes it.

Yura wants to choose a subset of assignments to maximize the total number of points. However, he has one problem: some assignments are too time-consuming. If Yura works on two assignments at positions $i$ and $j$ ($i \neq j$), there must be enough other assignments between them; otherwise, he will get distracted and fail to complete them.

Formally, for any two chosen assignments with indices $i$ and $j$, the following condition must hold: $|i - j| \gt \max(a_i, a_j)$.

Find the maximum total weight Yura can obtain by choosing a subset of assignments satisfying this condition.

尤拉有 $n$ 项家庭作业。对于每项作业，其权重 $a_i$ 是已知的——即尤拉完成该项作业所能获得的课程分数。

尤拉希望选择一个作业子集，以使总分最大化。但他面临一个问题：某些作业耗时过长。如果尤拉同时处理位置分别为 $i$ 和 $j$（$i \neq j$）的两项作业，则它们之间必须存在足够多的其他作业；否则，他将分心并无法完成这两项作业。

形式化地说，对任意两个被选中的、索引分别为 $i$ 和 $j$ 的作业，必须满足以下条件：$|i - j| \gt \max(a_i, a_j)$。

求尤拉在满足该条件的前提下，所能获得的最大总权重。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the elements of the array.

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——数组 $a$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）——数组的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the maximum total weight of the selected assignments.

对于每个测试用例，输出一个整数——所选作业的总权重的最大值。

In the first example, it is optimal to choose assignments with indices $1$ and $5$.

In the third example, it is optimal to choose assignments with indices $1$ and $6$.

在第一个例子中，选择索引为 $1$ 和 $5$ 的作业是最优的。

在第三个例子中，选择索引为 $1$ 和 $6$ 的作业是最优的。