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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/** Class: TrainsAndStatistic2.java
 *  @author
 *  @version 1.0 <p>
 *  Course:
 *  Written / Updated: Jun 27, 2016
 *
 *  This Class -
 *  Purpose -
 */
public class TrainsAndStatistic2 {

	public TrainsAndStatistic2() {
		try {
			BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

			//Read the first line
			int n = Integer.parseInt(rd.readLine());

			/* stations[i] = contains following information:
			 * from a given station #i, you can buy tickets to get other stations whose #'s are > i.
			 * Specifically, you can buy tickets to go from station i to stations i+1 thru stations[i].
			 *
			 * For example, let's say that stations[1] = 3.
			 * This means that, from station 1, you can buy tickets to go to either station 2 or station 3 directly.
			 *
			 * Another example: stations[4] = 5.
			 * From station 4, you can buy ticket to go to station 5 only.
			 *
			 * Note: stations[i] will ALWAYS contain a value that is > i. Thus, from a given station #i,
			 * it'll ALWAYS be possible to buy a ticket to station #i+1. */
			int stations[] = new int[n + 1];

			//Read second line
			String line = rd.readLine();
			StringTokenizer tokenizer = new StringTokenizer(line);

			//Save numbers on the 2nd line into array.
			for (int i = 1; i <= n - 1; i++) {
				int value = Integer.parseInt(tokenizer.nextToken());
				stations[i] = value;
			}
			stations[n] = n;

			rd.close();




			SegmentTree segTree = new SegmentTree(stations);

			/* This will be used for dynamic programming.
			 * p[i][j] = the min. no. of tickets to go from station i to station j, where 1 <= i < j <= n
			 * This array will be initialized with infinity. */
//			int[][] p = new int[n+1][n+1];
//			for (int[] _p : p) {
//				Arrays.fill(_p, Integer.MAX_VALUE);
//			}

			/* Let's fill up the p[][] array with some base cases.
			 * Note that p[i][i+1] will always equal 1, for every applicable i.
			 * For example, p[1][2] = 1, p[2][3] = 1, and so on.
			 *
			 * Read my comments above regarding stations[i] to see why this is true. */
//			for (int i = 1; i <= n - 1; i++) {
//				p[i][i+1] = 1;
//			}

			/* Recursive substructure for dynamic programming:
			 * 1) IF stations[i] >= j, then p[i][j] = 1.
			 * (For example, p[1][5] = 1 IFF stations[1] == 5, since this means that from station 1, you can buy tickets to go to
			 * station 2, station 3, station 4 or station 5 directly.)
			 *
			 * 2) Otherwise, p[i][j] = p[m][j] + 1, where:
			 * a) 1 <= i < m <= stations[i], where m indicates a station #,
			 * b) it's possible to travel DIRECTLY from station #i to station #m, and
			 * c) stations[m] has the maximum value out of all the stations one can travel directly from station #i.
			 * d) note that j can fall anywhere in the formula in (a) above as long as i < j. That is, any of the following are possible:
			 *    1 <= i < j <= m <= stations[i],
			 *    1 <= i < m < j <= stations[i],
			 *    1 <= i < m < stations[i] < j <= n
			 *
			 * FOR EXAMPLE, let's say there are six total stations, and
			 * stations[1] = 4, stations[2] = 3, stations[3] = 6, stations[4] = 5, stations[5] = 6.
			 * (There is no actual value for stations[6] because station #6 is the last station, but let's just say that stations[6] = 6.)
			 * Then, p[1][6] = p[3][6] + 1, because you can travel DIRECTLY from station 1 to station 3, AND because
			 * stations[3] has the maximum value out of all the stations one can travel directly from station 1.
			 * Some other examples:
			 * p[3][5] = 1 since stations[3] = station #6, and station #5 <= #6.
			 *
			 *=======================================================================================================================
			 * From the above example, we can generalize the following facts:
			 * (1) p[i][j]	 			 for i + 1 			 <= j <= m			 	equals 1
			 *     (Can go directly from #i to #m by definition, thus same is obviously true for #j.)
			 *
			 * (2) SUM of all p[i][j] 	 for i + 1 			 <= j <= m 				equals m - i
			 *     (Above is true since each p[i][j] for j in the above range is 1, as seen in (1).
			 *      So you have to sum up 1 + 1 + ... + 1 for a loop between i+1 and m, aka a total of m - i times.)
			 *
			 * (3) p[i][j]  			 for m + 1 			 <= j <= stations[i]   	equals p[m][j] = 1
			 *     (as long as j <= stations[i], can jump directly from #i to #j.)
			 *
			 * (4) p[i][j] 				 for stations[i] + 1 <= j <= n 				equals p[m][j] + 1
			 *     (see my comments above at the beginning of "Recursive substructure for dynamic programming:" above.)
			 *
			 * (5) SUM of all p[i][j]	 for m + 1 			 <= j <= n 				equals dp[m] + n - stations[i]
			 *     (where dp[m] is defined as the sum of all p[m][j] for m + 1 <= j <= n. But note that p[m][j] is simplified to a constant, 1,
			 *      for m + 1 <= j <= stations[i]. And as for stations[i] + 1 <= j <= n, p[m][j] is not simplified to a constant,
			 *      and there is + 1 at the end of it. So we have to add up + 1 a total of times for a loop from
			 *      stations[i] + 1 to n, AKA a total of n - stations[i] times. Note that aside from this adding up of + 1,
			 *      everything else is expressed in terms of p[m][j], so we can just express the sums of all the p[m][j]'s in terms
			 *      of a single variable, dp[m].
			 *      Thus, the SUM of all p[i][j] for m + 1 <= j <= n is simply dp[m] + (1 + 1 + ... + 1) = dp[m] + (n - stations[i]),
			 *      where dp[m] is the sum of ALL p[m][j] from m + 1 <= j <= n. And since (3) and (4) are both defined in terms of
			 *      p[m][j] already except that, in (4), we see the little + 1 at the end. So the 1's are all we have to worry about.)
			 *
			 *
			 * THEREFORE:
			 * (6) Sum of all p[i][j] 	 for j = i + 1, ..., n 						equals dp[i] = (m - i) + (dp[m] + n - stations[i])
			 * 														  			 				 =  dp[m] - (stations[i] - m) + n - i
			 * (We're simply adding up (2) and (5) here. Nothing more.)
			 *
			 * ===================================================================================================================================
			 * Now then, in order to save memory space, we will NOT actually be implementing p[i][j] array.
			 * Instead, we'll stick with a 1D array dp[i] as defined above.
			 * */


			/* dp[i] = the sum of the following:
			 * shortest path length from station i to station i+1,
			 * shortest path length from station i to station i+2,
			 * ...,
			 * shortest path length from station i to station n.
			 *
			 * Base case:
			 * dp[n] = sum of shortest path length from station n to station n = 0.
			 *
			 * Recursive substructure:
			 * See LONG comment above.
			 * */
			long[] dp = new long[n+1];

			dp[n] = 0;	//base case
			//We'll go backwards.
			for (int i = n-1; i >= 1; --i) {
				int m = segTree.maxQuery(i+1, stations[i])[1];
				dp[i] = dp[m] - (stations[i] - m) + n - i;
			}

//			int[] dp = new int[n];
//
//			dp[n-1] = 0;	//base case
//			//We'll go backwards.
//			for (int i = n-2; i >= 0; --i) {
//				int m = segTree.maxQuery(i+2, stations[i+1])[1];
//				dp[i] = dp[m-1] - (stations[i+1] - (m)) + n - i - 1;
//			}

			long sum = 0;
			for (int i = 0; i <= n; ++i) {
				sum += dp[i];
			}

			System.out.println(sum);
//			int gap = 2;
//			while (gap <= n - 1) {
//				for (int i = 1; i <= n - gap; i++) {
//					int j = i + gap;
//					if (stations[i] >= j) {
//						p[i][j] = 1;
//					} else {
//						for (int k = i+1; k <= j-1; k++) {
//							p[i][j] = Math.min(p[i][j], p[i][k] + p[k][j]);
//						}
//					}
//					//end if/else
//				}
//				//end for i
//
//				gap++;
//			}
//
//			/* Now sum up all the values in p[][] and output */
//			int sum = 0;
//			for (int i = 1; i <= n - 1; ++i) {
//				for (int j = i+1; j <= n; ++j) {
//					sum += p[i][j];
//				}
//			}
//			System.out.println(sum);

		} catch (IOException ioe) {
			ioe.printStackTrace();
		}
	}
	//end public TrainsAndStatistic()

	public static void main(String[] args) {

//		SegmentTree st = new SegmentTree(new int[]{3,8,1,2,4,6,9});
//		System.out.println(st.maxQuery(0, 2));
//		System.out.println(st.maxQuery(3, 3));
//		System.out.println(st.maxQuery(0, 5));
//		System.out.println(st.maxQuery(2, 4));
//		System.out.println(st.maxQuery(1, 5));
//		System.out.println(st.maxQuery(0, 6));
//		System.out.println(st.maxQuery(4, 6));
//		System.out.println(st.maxQuery(2, 5));
//		System.out.println(st.maxQuery(3, 5));
		new TrainsAndStatistic2();
	}
}

class SegmentTree {
	private class Node {
		Node left, right, parent;	//left child, right child, and parent of this Node
		int a, b;					//[a, b] indicates a range of interval pertaining to this Node, where a = min. and b = max.
		int[] maxValueAndStationNumber;

		Node() {
			this.left = null;
			this.right = null;
			this.parent = null;
			this.a = -1;
			this.b = -1;
			this.maxValueAndStationNumber = new int[]{Integer.MIN_VALUE, -1};
		}

		Node(Node left, Node right, Node parent) {
			this();		//invoke the no-arg constructor first.
			this.left = left;
			this.right = right;
			this.parent = parent;
		}

		Node(int min, int max) {
			this();	//invoke the no-arg constructor first.
			this.a = min;
			this.b = max;
		}

		void setLeft(Node left) {
			this.left = left;
		}

		void setRight(Node right) {
			this.right = right;
		}

		void setParent(Node parent) {
			this.parent = parent;
		}

		void setInterval(int min, int max) {
			this.a = min;
			this.b = max;
		}

		void setMaxValue(int value, int stationNum) {
			this.maxValueAndStationNumber[0] = value;
			this.maxValueAndStationNumber[1] = stationNum;
		}

		@Override
		public String toString() {
			return String.format("(interval:[%s,%s], maxValueAndStationNumber:%s)",
					               a,b, Arrays.toString(this.maxValueAndStationNumber));
		}

	}

	private Node root;
	private int[] arr;

	public SegmentTree(int[] arr) {
		root = new Node();
		this.arr = arr;
		buildTree(null, root, 1, arr.length - 1);
	}

	private int[] buildTree(Node parent, Node currNode, int minIndex, int maxIndex) {
		currNode.setParent(parent);
		currNode.setInterval(minIndex, maxIndex);
		if (minIndex == maxIndex) {	//means that currNode is a leaf node, no more children
			currNode.setMaxValue(this.arr[minIndex], minIndex);
			return currNode.maxValueAndStationNumber;
		}

		//If we get this far, it means minIndex < maxIndex. Split to left and right child
		int midIndex = (minIndex + maxIndex) / 2;
		Node leftChild = new Node();
		Node rightChild = new Node();
		currNode.setLeft(leftChild);
		currNode.setRight(rightChild);
		int[] maxFromLeftChild = buildTree(currNode, leftChild, minIndex, midIndex);
		int[] maxFromRightChild = buildTree(currNode, rightChild, midIndex + 1, maxIndex);
		if (maxFromLeftChild[0] > maxFromRightChild[0]) {
			currNode.setMaxValue(maxFromLeftChild[0], maxFromLeftChild[1]);
		} else {
			currNode.setMaxValue(maxFromRightChild[0], maxFromRightChild[1]);
		}
		return currNode.maxValueAndStationNumber;
	}
	//end private void buildTree

	/**
	 * Method: maxQuery
	 * @param a the index no. of the element contained in the array arr.
	 * @param b the index no. of the element contained in the array arr. It is assumed that a <= b.
	 * @return the max. value in the interval between arr[a] and arr[b] inclusive, where arr is an int array
	 *         used to build this SegmentTree.
	 */
	public int[] maxQuery(int requestedMin, int requestedMax) {
		return maxQuery(requestedMin, requestedMax, this.root);
	}

	/**
	 * Method: maxQuery. Overloaded helper method.
	 * @param a
	 * @param b
	 * @param minIndex
	 * @param maxIndex
	 * @return
	 */
	private int[] maxQuery(int requestedMin, int requestedMax, Node currNode) {
		if (currNode == null)
			return new int[]{Integer.MIN_VALUE, -1};
		int minIndex = currNode.a;
		int maxIndex = currNode.b;

		if (maxIndex < requestedMin || minIndex > requestedMax) {	//base case. out of range
			return new int[]{Integer.MIN_VALUE, -1};
		}
		if (minIndex >= requestedMin && maxIndex <= requestedMax) {	//base case. the requested interval indices "cover" the currentNode's minIndex and maxIndex
			return currNode.maxValueAndStationNumber;
		}

		int[] maxQueryFromLeft = maxQuery(requestedMin, requestedMax, currNode.left);
		int[] maxQueryFromRight = maxQuery(requestedMin, requestedMax, currNode.right);
		if (maxQueryFromLeft[0] > maxQueryFromRight[0]) {
			return maxQueryFromLeft;
		} else return maxQueryFromRight;

	}
	//end private int maxQuery
}