Long Jumps
Polycarp found under the Christmas tree an array $$$a$$$ of $$$n$$$ elements and instructions for playing with it:   At first, choose index $$$i$$$ ($$$1 \leq i \leq n$$$) — starting position in the array. Put the chip at the index $$$i$$$ (on the value $$$a_i$$$).  While $$$i \leq n$$$, add $$$a_i$$$ to your score and move the chip $$$a_i$$$ positions to the right (i.e. replace $$$i$$$ with $$$i + a_i$$$).  If $$$i > n$$$, then Polycarp ends the game. For example, if $$$n = 5$$$ and $$$a = [7, 3, 1, 2, 3]$$$, then the following game options are possible:   Polycarp chooses $$$i = 1$$$. Game process: $$$i = 1 \overset{+7}{\longrightarrow} 8$$$. The score of the game is: $$$a_1 = 7$$$.  Polycarp chooses $$$i = 2$$$. Game process: $$$i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8$$$. The score of the game is: $$$a_2 + a_5 = 6$$$.  Polycarp chooses $$$i = 3$$$. Game process: $$$i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6$$$. The score of the game is: $$$a_3 + a_4 = 3$$$.  Polycarp chooses $$$i = 4$$$. Game process: $$$i = 4 \overset{+2}{\longrightarrow} 6$$$. The score of the game is: $$$a_4 = 2$$$.  Polycarp chooses $$$i = 5$$$. Game process: $$$i = 5 \overset{+3}{\longrightarrow} 8$$$. The score of the game is: $$$a_5 = 3$$$. Help Polycarp to find out the maximum score he can get if he chooses the starting index in an optimal way.
The first test case is explained in the statement.In the second test case, the maximum score can be achieved by choosing $$$i = 1$$$.In the third test case, the maximum score can be achieved by choosing $$$i = 2$$$.In the fourth test case, the maximum score can be achieved by choosing $$$i = 1$$$.
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — elements of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output on a separate line one number — the maximum score that Polycarp can get by playing the game on the corresponding array according to the instruction from the statement. Note that Polycarp chooses any starting position from $$$1$$$ to $$$n$$$ in such a way as to maximize his result.
import math
import cmath
import string

def sieve(n):
    l = [0] * (n + 1)
    l[0] = l[1] = 1
    for i in range(2, int(n ** 0.5) + 1):
        if not l[i]:
            for j in range(i * i, n + 1, i):
                l[j] = 1
    return [i for i in range(n + 1) if l[i] == 0]

def sieveOptemised(n, prime):
    l = [0] * (n + 1)
    l[0] = l[1] = 1
    for i in range(2, n):
        if not l[i]:
            prime.append(i)
        for j in range(len(prime)):
            if i * prime[j] >= n:
                break
            l[i * prime[j]] = 1
            if i % prime[j] == 0:
                break

def XOR(n):
    return [n, 1, n + 1, 0][n % 4]

def isprime(n):
    return all([False for i in range(2, n) if n % i == 0]) and (not n < 2)

def searchBinary(lis, l, r, e):
    ans = 0
    while l <= r:
        m = (l + r) // 2
        if lis[m][0] > e:
            r = m - 1
        else:
            l = m + 1
            ans = l
    return ans

def f(l, i, j, n, m):
    c = l[i][j]
    i1 = i
    j1 = j
    i2 = i
    j2 = j
    i3 = i
    j3 = j
    i4 = i
    j4 = j
    while i1 > 0 and j1 > 0:
        i1 -= 1
        j1 -= 1
        c += l[i1][j1]
    while i2 < n - 1 and j2 < m - 1:
        i2 += 1
        j2 += 1
        c += l[i2][j2]
    while i3 > 0 and j3 < m - 1:
        i3 -= 1
        j3 += 1
        c += l[i3][j3]
    while i4 < n - 1 and j4 > 0:
        i4 += 1
        j4 -= 1
        c += l[i4][j4]
    return c

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def binarySearch(lis, l, r, e):
    while l <= r:
        m = (l + r) // 2
        if lis[m] == e:
            return 1
        elif lis[m] > e:
            r = m - 1
        else:
            l = m + 1
    return 0

def isSqrt(n):
    for i in range(1, int(n ** 0.5) + 2):
        if i * i == n:
            return True
    return False
result = list(string.ascii_lowercase)
alpha = {}
for i in range(26):
    alpha[result[i]] = i + 1
import random

def fermatTesting(n, k):
    if n == 1 or n == 4:
        return False
    elif n == 2 or n == 3:
        return True
    for i in range(k):
        a = random.randint(2, n - 2)
        if pow(a, n - 1, n) != 1:
            return False
    return True

def check_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(n)) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

def mex(l):
    ll = l.copy()
    ll.sort()
    for i in range(len(l)):
        if i != ll[i]:
            return i
    return len(l)
aa = []
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    ans = l.copy()
    for i in range(n - 1, -1, -1):
        if i + l[i] < n:
            ans[i] += ans[i + l[i]]
    aa.append(max(ans))
for i in aa:
    print(i)
import sys
import heapq
input = sys.stdin.readline
from collections import Counter, defaultdict

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def main():
    length = inp()
    array = inlt()
    for i in range(length - 1, -1, -1):
        newPlace = i + array[i]
        if newPlace < length:
            array[i] += array[newPlace]
    print(max(array))
if __name__ == '__main__':
    t = inp()
    for _ in range(t):
        main()
import sys
import heapq
input = sys.stdin.readline
from collections import Counter, defaultdict

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def main():
    length = inp()
    array = inlt()
    for i in range(length - 1, -1, -1):
        if i + array[i] < length:
            array[i] = array[i] + array[i + array[i]]
    print(max(array))
if __name__ == '__main__':
    t = inp()
    for _ in range(t):
        main()