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.

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

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