Maximizing Coins in an Unlocking Game

You are given an array \(a\) of length \(n\). Initially, only \(a_1\) is unlocked. An index variable \(i\) is initialized as \(1\). You then play the following game on the array:

• If \(a_i\) is not unlocked, the game ends.
• Otherwise, you have two choices at index \(i\):
  • You can unlock the range of elements \(a_{i+1}\) to \(a_{i+a_i}\) (if \(a_i>0\); note that if \(a_i=0\) no new elements are unlocked), or
  • You can collect \(a_i\) coins.
  After performing your choice, you increase \(i\) by 1.

Your task is to determine the maximum number of coins you can obtain when the game ends. Note that unlocking an element makes it available for decisions later. Also, if the unlocking range goes beyond index \(n\), consider that all elements from \(i+1\) to \(n\) are unlocked.

Input Format: The first line contains an integer \(n\) \( (1 \le n \le \text{small})\). The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\). The array is 1-indexed and initially only \(a_1\) is unlocked.

Output Format: Output a single integer representing the maximum coins that can be collected.

inputFormat

The input begins with an integer \(n\) on the first line, representing the length of the array. The second line contains \(n\) space‐separated integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output one integer: the maximum number of coins that can be obtained by playing the game optimally.

sample

1
5

5