| Codeforces Round 174 (Div. 1) |
|---|
| Закончено |
Фермер Джон только что дал коровкам поиграться с программой! Программа содержит две целочисленные переменные x и y. Ей подается на вход последовательность положительных целых чисел a1, a2, ..., an, в зависимости от которой она выполняет следующие операции:
- Изначально x = 1 и y = 0. Если после какого-то шага x ≤ 0 или x > n, то программа немедленно завершается.
- Программа одновременно увеличивает x и y на ax.
- Затем программа увеличивает y на ax, уменьшая x на ax.
- Программа попеременно выполняет шаги 2 и 3 (сначала 2, затем 3), пока не завершится (она может никогда не завершиться). Таким образом, последовательность шагов может начаться так: шаг 2, шаг 3, шаг 2, шаг 3, шаг 2 и так далее.
Коровки все же не очень хорошо считают, и поэтому они хотят разобраться, как работает программа. Пожалуйста, помоги им!
Дана последовательность a2, a3, ..., an. Предположим, что для каждого i (1 ≤ i ≤ n - 1) мы запускаем программу на последовательности i, a2, a3, ..., an. Для каждого такого запуска выведите итоговое значение y, если программа завершится, или -1, если программа не завершится.
Первая строка содержит единственное целое число, n (2 ≤ n ≤ 2·105). Следующая строка содержит n - 1 целых чисел через пробел, a2, a3, ..., an (1 ≤ ai ≤ 109).
Выведите n - 1 строк. В i-ой строке выведите требуемое значение, когда программа запускается на последовательности i, a2, a3, ...an.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
4
2 4 1
3
6
8
3
1 2
-1
-1
В первом примере
- Для i = 1, x изменяется следующим образом:
, y становится 1 + 2 = 3. - Для i = 2, x изменяется следующим образом:
, y становится 2 + 4 = 6. - Для i = 3, x изменяется следующим образом:
, y становится 3 + 1 + 4 = 8.
