Поликарп нашёл под ёлкой массив \(a\) из \(n\) элементов и инструкцию для игры с ним:
- Выбери число \(i\) (\(1 \leq i \leq n\)) — стартовую позицию в массиве. Помести фишку на позицию \(i\) (на элемент \(a_i\));
- Пока \(i \leq n\), прибавь к своему результату значение \(a_i\) и переместись на \(a_i\) вправо (т.е. замени \(i\) на \(i + a_i\));
- Если \(i > n\), то Поликарп заканчивает игру.
Например, если \(n = 5\) и \(a = [7, 3, 1, 2, 3]\), тогда следующие варианты игр возможны:
- Поликарп выбирает \(i = 1\). Процесс игры: \(i = 1 \overset{+7}{\longrightarrow} 8\). Результат игры: \(a_1 = 7\).
- Поликарп выбирает \(i = 2\). Процесс игры: \(i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8\). Результат игры: \(a_2 + a_5 = 6\).
- Поликарп выбирает \(i = 3\). Процесс игры: \(i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6\). Результат игры: \(a_3 + a_4 = 3\).
- Поликарп выбирает \(i = 4\). Процесс игры: \(i = 4 \overset{+2}{\longrightarrow} 6\). Результат игры: \(a_4 = 2\).
- Поликарп выбирает \(i = 5\). Процесс игры: \(i = 5 \overset{+3}{\longrightarrow} 8\). Результат игры: \(a_5 = 3\).
Помогите Поликарпу узнать, какой максимальный результат он может получить, если он выбирает стартовую позицию оптимально.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите одно число — максимальный результат, который Поликарп может получить, сыграв в игру на соответствующем массиве по инструкции из условия. Обратите внимание, что Поликарп выбирает любую стартовую позицию от \(1\) до \(n\) таким образом, чтобы максимизировать свой результат.
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных максимальный результат достигается при выборе \(i = 1\).
В третьем наборе входных данных максимальный результат достигается при выборе \(i = 2\).
В четвёртом наборе входных данных максимальный результат достигается при выборе \(i = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
7 3 1 2 3
3
2 1 4
6
2 1000 2 3 995 1
5
1 1 1 1 1
|
7
6
1000
5
|