Thống kê tàu điện

Trong thành phố có $n$ ga tàu đánh số từ $1$ đến $n$. Tại ga thứ $i$ (với $1\le i<n$) người ta chỉ bán vé đi tới các ga từ $i+1$ đến $a_i$ (bao gồm cả hai đầu mút). Ga cuối cùng không bán vé nào.

Với hai ga $i<j$, gọi ${\rho }_{i,j}$ là số vé tối thiểu cần mua để đi từ ga $i$ tới ga $j$. Do luật bán vé, từ mỗi ga luôn có thể đi tới mọi ga có chỉ số lớn hơn (có thể phải đổi tàu nhiều lần), nên ${\rho }_{i,j}$ luôn xác định.

Hãy tính tổng của tất cả các giá trị ${\rho }_{i,j}$ trên mọi cặp $1\le i<j\le n$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: số lượng ga.
• Dòng thứ hai chứa $n-1$ số nguyên $a_1,a_2,\dots ,a_{n-1}$, trong đó $a_i$ là ga xa nhất mà từ ga $i$ có thể mua vé đi tới trực tiếp.

Dữ liệu ra

• In ra một số nguyên: tổng ${\rho }_{i,j}$ trên mọi cặp $1\le i<j\le n$.

Ràng buộc

• $2\le n\le 100000$
• $i+1\le a_i\le n$ với mọi $1\le i<n$
• Kết quả có thể rất lớn, cần dùng kiểu số nguyên 64-bit.

Ví dụ