Vasya commutes by train every day. There are n train stations in the city, and at the i-th station it's possible to buy only tickets to stations from i + 1 to ai inclusive. No tickets are sold at the last station.

Let ρi, j be the minimum number of tickets one needs to buy in order to get from stations i to station j. As Vasya is fond of different useless statistic he asks you to compute the sum of all values ρi, j among all pairs 1 ≤ i < j ≤ n.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of stations.

The second line contains n - 1 integer ai (i + 1 ≤ ai ≤ n), the i-th of them means that at the i-th station one may buy tickets to each station from i + 1 to ai inclusive.

Output

Print the sum of ρi, j among all pairs of 1 ≤ i < j ≤ n.

Examples

Input

4
4 4 4


Output

6


Input

5
2 3 5 5


Output

17

Note

In the first sample it's possible to get from any station to any other (with greater index) using only one ticket. The total number of pairs is 6, so the answer is also 6.

Consider the second sample: 

  * ρ1, 2 = 1
  * ρ1, 3 = 2
  * ρ1, 4 = 3
  * ρ1, 5 = 3
  * ρ2, 3 = 1
  * ρ2, 4 = 2
  * ρ2, 5 = 2
  * ρ3, 4 = 1
  * ρ3, 5 = 1
  * ρ4, 5 = 1



Thus the answer equals 1 + 2 + 3 + 3 + 1 + 2 + 2 + 1 + 1 + 1 = 17.

import java.util.*;
import java.io.*;

public class Round_353E_Div2 {

	static BufferedReader br;
	static PrintWriter out;
	static StringTokenizer st;

	static int N;
	static int[] val, max, index;
	static long[] dp;
	
	public static void main (String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(new OutputStreamWriter(System.out));
		//br = new BufferedReader(new FileReader("in.txt"));
		//out = new PrintWriter(new FileWriter("out.txt"));

		N = readInt();
		
		
		max = new int[4 * N];
		
		val = new int[N + 1];
		dp = new long[N + 1];
		
		for (int i = 1; i < N; i++)
			val[i] = readInt();
		val[N] = N;
		
		build(1, 1, N);
		
		long ans = 0;
		for (int i = N - 1; i >= 1; i--) {
			int s = query(1, 1, N, i + 1, val[i]);
			long best = dp[s] + N - i - (val[i] - s);
			dp[i] = best;
			ans += best;
		}
		
		out.println(ans);
		out.close();
	}

	static void build (int n, int l, int r) {
		if (l == r) {
			max[n] = l;
			return;
		}
		
		int mid = (l + r) >> 1;
		build(n << 1, l, mid);
		build(n << 1 | 1, mid + 1, r);
		
		if (val[max[n << 1]] >= val[max[n << 1 | 1]])
			max[n] = max[n << 1];
		else
			max[n] = max[n << 1 | 1];
	}
	
	static int query (int n, int l, int r, int ql, int qr) {
		if (l == ql && r == qr) 
			return max[n];
		
		int mid = (l + r) >> 1;
		if (qr <= mid)
			return query(n << 1, l, mid, ql, qr);
		else if (ql > mid)
			return query(n << 1 | 1, mid + 1, r, ql, qr);
		else {
			int s1 = query(n << 1, l, mid, ql, mid);
			int s2 = query(n << 1 | 1, mid + 1, r, mid + 1, qr);
			if (val[s1] >= val[s2])
				return s1;
			else
				return s2;
		}
	}
	
	static class State {
		int index, min;
		State (int min, int index) {
			this.min = min;
			this.index = index;
		}
	}
	
	static String next () throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine().trim());
		return st.nextToken();
	}

	static long readLong () throws IOException {
		return Long.parseLong(next());
	}

	static int readInt () throws IOException {
		return Integer.parseInt(next());
	}

	static double readDouble () throws IOException {
		return Double.parseDouble(next());
	}

	static char readCharacter () throws IOException {
		return next().charAt(0);
	}

	static String readLine () throws IOException {
		return br.readLine().trim();
	}
}
