There are many possible solutions. One of them is just to print $$$2,3,…,n,1$$$.

import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    ans = []
    for i in range(2, n + 1):
        ans.append(i)
    ans.append(1)
    print(*ans)

Let $$$score(i)$$$ be the result of the game if we chose $$$i$$$ as the starting position. Let's look at some starting position $$$i$$$. After making a move from it, we will get $$$a[i]$$$ points and move to the position $$$i+a[i]$$$. Let $$$j = i+a[i]$$$, if this is still inbounds we will apply the same operation until it gets out of bounds where the score is $$$0$$$. Formally, $$$score(i)=score(i+a[i])+a[i]$$$.

So lets consider every index as a starting position and track the maximum score we can get.

import sys, threading
input = lambda: sys.stdin.readline().strip()


def main():
    
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))

        memo = [-1]*n

        def dp(idx):
            # base case
            if idx >= n:
                return 0

            if memo[idx] != -1:
                return memo[idx]
            
            memo[idx] = dp(idx + a[idx]) + a[idx]
            return memo[idx]
        
        ans = 0
        for start in range(n):
            ans = max(ans, dp(start))
        
        print(ans)

    
if __name__ == '__main__':
    
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

What should our state be?

At each state, what are our possible options?

How does our state change after choosing one of the options?

We are going to use dynamic programming to solve this problem. Our state is going to be $$$n$$$. At each step, we have 3 choices: take $$$a$$$, $$$b$$$, or $$$c$$$. Our recurrence relation is going to be:

$$$dp(n)= 1+max⁡(dp(n−a),dp(n−b),dp(n−c))$$$

For our base cases, if $$$n$$$ becomes 0, we return 0. Another base case is if $$$n$$$ is less than 0, we return $$$-inf$$$, which is a very small number because we want the maximum answer. This answer will ensure that we do not consider this path.

from functools import lru_cache
import sys
import threading

def main():
    n,a,b,c = list(map(int,input().split()))

    memo = [-1 for i in range(n + 1)]
    
    def dp(n):
        
        if n < 0:
            return -float('inf')
        if n == 0:
            return 0
        
        if memo[n] != -1:
            return memo[n]
        
        memo[n] = 1 + max(dp(n - a),dp(n - b),dp(n - c))
        
        return memo[n]
    
    print(dp(n))
    
sys.setrecursionlimit( 1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target = main)
main_thread.start()
main_thread.join()

One thing we can notice is that if we choose a number $$$x$$$, it means we can't choose $$$x - 1$$$ and $$$x + 1$$$. In other words, this means we can't choose two consecutive values. Another point is that once we choose $$$x$$$, choosing it multiple times wouldn't have any disadvantage on our score. Therefore, if we decide to choose $$$x$$$, we have to choose all instances of $$$x$$$, and the score if we choose all $$$x$$$ is going to be $$$\text{count}[x] \times x$$$.

For every number between 1 and $$$\max(a)$$$:

$$$f(i) = \max(f(i - 1), f(i - 2) + \text{count}[i] \times i), \quad 2 \leq i \leq n;$$$

$$$f(1) = \text{count}[1];$$$

$$$f(0) = 0;$$$

The answer is $$$f(n)$$$.

import sys, threading
from collections import Counter

input = lambda: sys.stdin.readline().strip()

def main():
    memo = {}
    n = int(input())
    cnt = Counter(map(int,input().split()))
    def dp(n):

        if n <= 1:
            return cnt[n]
        if n not in memo:
            memo[n] = max(dp(n -1), dp(n -2) + cnt[n]*n)
    	return memo[n]
    print(dp(max(cnt.keys())))
    
if __name__ == '__main__':
    
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

Let's define ( S(k) ) as the sum of elements \sum\limits_{i = k}^{n}{a_i}

. Additionally, let $$$pi$$$ denote the starting position of the $$$( ith)$$$ subarray, where $$$( p1 = 1)$$$ and $$$( pi < pi+1)$$$.

Now, consider the transformation: $$$\sum_{i=1}^{n}{a_i \cdot f(i)} = 1 \cdot (S(p_1) - S(p_2)) + 2 \cdot (S(p_2) - S(p_3)) + \dots + k \cdot (S(p_k) - 0) = \ = S(p_1) + (2 - 1) S(p_2) + (3 - 2) S(p_3) + \dots + (k - (k - 1))) S(p_k) = \ = S(p_1) + S(p_2) + S(p_3) + \dots + S(p_k)$$$

So, our objective is to select the sum of the entire array ( S(1) ) and ( k — 1 ) different suffix sums to maximize their total sum. Consequently, we can simply select the (k — 1) maximum suffix sums along with the sum of the entire array.

Time Complexity: $$$O(n)$$$ time. Space Complexity: $$$O(n)$$$

def main():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))

    sfxSum = [nums[-1]]
    for i in range(n - 2, -1, -1):
        sfxSum.append(sfxSum[-1] + nums[i])
    
    ans = sfxSum.pop()
    sfxSum.sort(reverse=True)
    for i in range(k - 1):
        ans += sfxSum[i]
    print(ans)

if __name__ == '__main__':
    main()