Một chương trình trò chơi trên máy tính được mô tả như sau: Cho 2 số ~X, Y~ và một dãy số nguyên dương ~a_1, a_2, \dots, a_n~. Chương trình thực hiện các bước sau:

1. Ban đầu ~X = 1~ và ~Y = 0~. Sau một số bước, nếu ~X \le 0~ hoặc ~X > n~ thì lập tức dừng chương trình.
2. Tăng cả ~X~ và ~Y~ lên một lượng là ~a_X~.
3. Giảm ~X~ đi một lượng là ~a_X~ và tăng ~Y~ lên một lượng là ~a_X~.
4. Chương trình thực hiện lần lượt bước 2 và bước 3 liên tục đến khi nào không thỏa mãn.

Yêu cầu: Cho dãy ~a_2, a_3, \dots, a_n~. Giả sử với mỗi ~i~ (~1 \le i \le n-1~), gán ~a_1 = i~, chạy chương trình trên với dãy ~a_1, a_2, \dots, a_n~. Với mỗi giá trị, in ra giá trị cuối cùng của ~Y~, in ~-1~ nếu chương trình không bao giờ kết thúc.

Input

• Dòng đầu tiên cho số nguyên ~n~ (~2 \le n \le 2 \times 10^5~)
• Dòng thứ 2 chứa ~n-1~ số nguyên ~a_2, a_3, \dots, a_n~ (~1 \le a_i \le 10^9~)

Output

• In ra ~n-1~ dòng, dòng ~i~ ứng với kết quả của ~Y~ khi gán ~a_1 = i~.

Sample Input 1

4
2 4 1

Sample Output 1

3
6
8