Bạn ~P~ sống ở thành phố ~A~. Thành phố ~A~ có ~n~ trạm xe buýt, tại trạm xe buýt thứ ~i~ chỉ có thể mua vé để đi đến các trạm từ ~i+1~ tới ~a_i~. Trạm cuối sẽ không bán vé.

Trong lớp tin học, bạn ~P~ nhận được một bài tập như sau: cho ~D_{i, j}~ là số vé xe buýt ít nhất cần mua để đi từ trạm ~i~ đến trạm ~j~. Hãy tính tổng tất cả các ~D_{i, j}~ ~(1 \le i < j \le n)~.

Yêu cầu: hãy giúp bạn ~P~ tính tổng tất cả các ~D_{i, j}~ ~(1 \le i < j \le n)~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 10^6)~ là số trạm xe buýt.
• Dòng tiếp theo chứ ~n-1~ số nguyên ~a_1, a_2, \dots, a_{n-1}~ ~(i+1 \le a_i \le n)~, ~a_i~ có nghĩa là tại trạm thứ ~i~ chỉ có thể mua vé để đi đến các trạm từ ~i + 1~ đến ~a_i~.

Kết quả ra

• In ra một số nguyên duy nhất là tổng tìm được.

Ràng buộc

• Có ~40\%~ số test có ~1 \le n \le 5\times10^3~.
• Còn lại ~60\%~ số test không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

4
3 3 4 

Kết quả ra

8

Giải thích

~D_{1, 2} = 1~

~D_{1, 3} = 1~

~D_{1, 4} = 2~

~D_{2, 3} = 1~

~D_{1, 4} = 2~

~D_{3, 4} = 1~

Kết quả của bài 1 + 1 + 2 + 1 + 2 + 1 = 8