← 返回题目列表

Codeforces · 283/B

B. 牛计划

中文机器翻译题面 查看原题

农夫约翰刚刚给奶牛们提供了一个可以玩的程序!该程序包含两个整数变量 x 和 y,并对正整数序列 a1, a2, ..., an 执行以下操作:

1. 最初,x = 1且y = 0。如果在任何步骤之后x ≤ 0或x > n,则程序立即终止。
2. 程序将 x 和 y 同时增加等于 ax 的值。
3. 程序现在将 y 增加 ax,同时将 x 减少 ax。
4. 程序重复执行步骤 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 说明符。

示例

输入 #1

4
2 4 1

输出 #1

3
6
8

输入 #2

3
1 2

输出 #2

-1
-1

注意

在第一个样本中

1. 对于 i = 1,  x 变为 $$1 \rightarrow 2 \rightarrow 0$$,y 变为 1 + 2 = 3。
2. 对于 i = 2,  x 变为 $$1 \rightarrow 3 \rightarrow - 1$$,y 变为 2 + 4 = 6。
3. 对于 i = 3,  x 变为 $$1 \rightarrow 4 \rightarrow 3 \rightarrow 7$$,y 变为 3 + 1 + 4 = 8。