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 - This is the efficient version.
 *  Verdict: VALID
 */
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] should 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.
			 * NOTE: we'll start at index i = 1 instead of i = 0.
			 * This is just a choice I made so it's easier and more straightforward to think of station #1
			 * as being as index #1, and so on.
			 *
			 * Also NOTE that i also goes up to n - 1 in the loop. This is because
			 * the last station -- i.e. station #n -- does not sell any tickets to go to any station beyond itself.
			 * (indeed, there is no station #n+1; hence, n is the last station)
			 * Thus, it's not necessary to save a value for station[n]. */
			for (int i = 1; i <= n - 1; i++) {
				int value = Integer.parseInt(tokenizer.nextToken());
				stations[i] = value;
			}

			rd.close();	//close the buffer reader.

			/* Recall the dynamic programming substructure from TrainsAndStatistic.java:
			 * p[i][j] = the min. no. of tickets to go from station i to station j, where 1 <= i < j <= n
			 * This substructure was probably correct, but takes up too much memory.
			 * For example, if there are 100,000 train stations (that is, n = 100,000), then
			 * initializing a 2D array like the above will take up 100,000 * 100,000 memory!
			 * So we'll see if we can do better. Keep reading....
			 *
			 * Convince yourself that the following are all true:
			 * 1) IFF 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
			 * DIRECTLY to station 2, station 3, station 4, station 5, or possibly beyond.)
			 *
			 * 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
			 *    So we'll have to explore each of the above possibilities for j, and we'll do so soon.
			 *    But FIRST, let's look at some examples.
			 *
			 * 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.)
			 * Then, p[1][6] = p[3][6] + 1 (which equals 2 in this case), 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.
			 * Another example: p[3][5] = 1 since it's given that stations[3] = 6, and 5 <= 6.
			 *
			 *=======================================================================================================================
			 * From the above examples, we can generalize the following facts
			 * (now we get to consider all the possibilities for j as we mentioned above):
			 * (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.
			 *      Note that in this situation, p[m][j] = 1 as well. Convince yourself of why this is true by
			 *      thinking of some examples on your own.)
			 *
			 * (4) p[i][j] 				 for stations[i] + 1 <= j <= n 				equals p[m][j] + 1
			 *     (see near the beginning of my comments herein for why this is true.)
			 *
			 * (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] in (3) above. And as for stations[i] + 1 <= j <= n in (4), 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 (the combination of (3) and (4) above).
			 *      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 -- and we expressed all the + 1's as n - stations[i].
			 *      Thus we have the equation dp[m] + (n - stations[i]) given in (5).)
			 *
			 *
			 * 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
			 * (but you should keep in mind the logic and meaning of p[i][j] as discussed above, because that's how
			 * we'll derive the more efficient dynamic programming substructure of dp[i]).
			 *
			 * Instead, we'll stick with a 1D array dp[i]:
			 *
			 * 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.
			 *
			 * In other words, dp[i] = sum of all p[i][j] for i + 1 <= j <= n. (Compare with dp[m] discussed above)
			 *
			 * Base case:
			 * dp[n] = sum of shortest path length from station n to station n = 0.
			 *
			 * Recursive substructure: dp[i] = dp[m] - (stations[i] - m) + n - i
			 * See the LONG comment above for how we derive the recursive substructure.
			 * */
			long[] dp = new long[n+1];	//We'll designate a long[] instead of an int[] array, because the number can get pretty large...

			/* We need a segment tree to calculate the value of m quickly.
			 * Again, what is m? You can read the LONG comment above, for read on for a summary:
			 *
			 * 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.
			 *
			 * See below for the SegmentTree class. Read TrainsAndStatistic - Segment Tree Tutorial.pdf for how it works. */
			SegmentTree segTree = new SegmentTree(stations);

			dp[n] = 0;	//base case
			/* We'll go backwards since the recursive substructure requires it.
			 * Why? Because dp[i] requires that we know the value of dp[m], and i < m
			 * (read the LONG comment above carefully to convince yourself of this) */
			for (int i = n - 1; i >= 1; --i) {
				int m = segTree.maxQuery(i+1, stations[i])[1];	//using segment tree to get value of m for the current i
				dp[i] = dp[m] - (stations[i] - m) + n - i;	//the recursive substructure that we figured out via the LONG comment above
			}


			long sum = 0;	//now it's time to add them up. Initialize a long sum instead of an int...numbers can get pretty large.
			for (int i = 0; i <= n; ++i) {
				sum += dp[i];
			}

			System.out.println(sum);		//Finally this is our output! WE'RE DONE.
		} catch (IOException ioe) {
			ioe.printStackTrace();
		}
	}
	//end public TrainsAndStatistic()

	public static void main(String[] args) {

		/* OPTIONAL: testing segment tree for correctness. */
//		SegmentTree st = new SegmentTree(new int[]{3,8,1,2,4,6,9});
//		System.out.println(st.maxQuery(0, 2)[0]);	//expected: 8
//		System.out.println(st.maxQuery(3, 3)[0]);	//expected: 2
//		System.out.println(st.maxQuery(0, 5)[0]);	//expected: 8
//		System.out.println(st.maxQuery(2, 4)[0]);	//expected: 4
//		System.out.println(st.maxQuery(1, 5)[0]);	//expected: 8
//		System.out.println(st.maxQuery(0, 6)[0]);	//expected: 9
//		System.out.println(st.maxQuery(4, 6)[0]);	//expected: 9
//		System.out.println(st.maxQuery(2, 5)[0]);	//expected: 6
//		System.out.println(st.maxQuery(3, 5)[0]);	//expected: 6
		new TrainsAndStatistic2();
	}
}

/**
 * class: SegmentTree
 * @author PP
 * A binary tree that takes in an array of ints.
 * Can answer queries about the max. value in certain interval of indices, e.g.
 * max value in index 1 thru 4, index 6 thru 7, index 8 thru 8, etc.
 *
 * NOTE: There are many different varieties of segment trees. The one that I made up
 * can answer queries about the max. value in some interval.
 * Other types of segment trees include: Min-query, Sum-query, etc.
 *
 * NOTE: Read file tilted TrinasAndStatistic - Segment Tree Tutorial.pdf carefully for a general tutorial
 * on how Segment Trees work.
 *
 * NOTE: My version of Segment Tree does not implement the "update" function because it's not needed for this problem.
 */
class SegmentTree {

	/**
	 * class: Node. Inner class.
	 * @author PP
	 */
	private class Node {
		Node left, right, parent;	//left child, right child, and parent of this Node. Parent isn't strictly needed for this problem. Whatever eh.
		int a, b;					//[a, b] indicates a range of interval pertaining to this Node, where a = min. and b = max.

		/* an array consisting of 2 elements: the max. value, and the corresponding station number.
		 * For example, if stations[2] = 6 happens to be the max. value, then the below array will contain [6, 2] */
		int[] maxValueAndStationNumber;

		/**
		 * Constructor.
		 */
		Node() {
			this.left = null;
			this.right = null;
			this.parent = null;
			this.a = -1;
			this.b = -1;
			this.maxValueAndStationNumber = new int[]{Integer.MIN_VALUE, -1};	//initialize min. value and an invalid index.
		}

		/**
		 * Overloaded constructors. Not needed for this problem.
		 */
//		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;
//		}

		/**
		 * Method: setLeft. Sets the left child of this node.
		 * @param left
		 */
		void setLeft(Node left) {
			this.left = left;
		}

		/**
		 * Method: setRight. Sets the right child of this node.
		 * @param right
		 */
		void setRight(Node right) {
			this.right = right;
		}

		/**
		 * Method: setParent. Sets the parent of this node.
		 * @param parent
		 */
		void setParent(Node parent) {
			this.parent = parent;
		}

		/**
		 * Method: setInterval. Sets the min. and max. interval of this node.
		 * @param min
		 * @param max
		 */
		void setInterval(int min, int max) {
			this.a = min;
			this.b = max;
		}

		/**
		 * Method: setMaxValue. Sets the max. value and the station number corresponding to it.
		 * @param value
		 * @param stationNum
		 */
		void setMaxValue(int value, int stationNum) {
			this.maxValueAndStationNumber[0] = value;
			this.maxValueAndStationNumber[1] = stationNum;
		}

		/**
		 * For debugging
		 */
		@Override
		public String toString() {
			return String.format("(interval:[%s,%s], maxValueAndStationNumber:%s)",
					               a,b, Arrays.toString(this.maxValueAndStationNumber));
		}
	}
	//end private class Node

	private Node root;	//The root of this segment tree
	private int[] arr;	//the array that we'll use to build this segment tree.

	/**
	 * Constructor.
	 * @param arr
	 */
	public SegmentTree(int[] arr) {
		root = new Node();
		this.arr = arr;

		/* Invoke recursive function. Note that the parameter re: index range is from
		 * 1 to arr.length - 1, instead of from 0 to arr.length - 1.
		 * This is because I chose to have the array start at index 1 instead of index 0
		 * for convenience. Thus, index 0 is basically a "null" index and should be ignored. */
		buildTree(null, root, 1, arr.length - 1);
	}

	/**
	 * Method: buildTree
	 * @param parent parent Node
	 * @param currNode current Node
	 * @param minIndex starting index of an interval
	 * @param maxIndex ending index of an interval
	 * @return an int[] array containing two elements:
	 * 		   1) the max. value within the interval;
	 * 		   2) the index # (which stands for the station #) of this.arr containing that max. value
	 */
	private int[] buildTree(Node parent, Node currNode, int minIndex, int maxIndex) {
		currNode.setParent(parent);
		currNode.setInterval(minIndex, maxIndex);
		if (minIndex == maxIndex) {	//Base case. means that currNode is a leaf node, so this node has no children
			currNode.setMaxValue(this.arr[minIndex], minIndex);	//since minIndex == maxIndex, we could also use maxIndex. Doesn't matter..
			return currNode.maxValueAndStationNumber;
		}

		//If we get this far, it means minIndex < maxIndex. Split the interval in half and create left and right child
		int midIndex = (minIndex + maxIndex) / 2;
		Node leftChild = new Node();
		Node rightChild = new Node();
		currNode.setLeft(leftChild);
		currNode.setRight(rightChild);

		//Recursive calls to buildTree for left and right child, and get their max values from each.
		int[] maxFromLeftChild = buildTree(currNode, leftChild, minIndex, midIndex);
		int[] maxFromRightChild = buildTree(currNode, rightChild, midIndex + 1, maxIndex);

		//compare the max. values and see which is greater
		if (maxFromLeftChild[0] > maxFromRightChild[0]) {
			currNode.setMaxValue(maxFromLeftChild[0], maxFromLeftChild[1]);
		} else {
			currNode.setMaxValue(maxFromRightChild[0], maxFromRightChild[1]);
		}
		return currNode.maxValueAndStationNumber;	//return the array containing the max value and station number.
	}
	//end private void buildTree

	/**
	 * Method: maxQuery
	 * @param requestedMin the index no. of the element contained in the array arr.
	 * @param requestedMax the index no. of the element contained in the array arr.
	 *        It is assumed that requestedMin <= requestedMax.
	 * @return the max. value in the interval between arr[requestedMin] and arr[requestedMax] 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);	//invoke helper method
	}

	/**
	 * Method: maxQuery. Overloaded recursive helper method.
	 * @param requestedMinIndex the index no. of the element contained in the array arr.
	 * @param requestedMaxIndex the index no. of the element contained in the array arr.
	 * @param currNode the current Node.
	 * @return the max. value in the interval between arr[requestedMin] and arr[requestedMax] inclusive, where arr is an int array
	 *         used to build this SegmentTree.
	 */
	private int[] maxQuery(int requestedMinIndex, int requestedMaxIndex, Node currNode) {
		if (currNode == null) {	//base case. return minimum value and invalid index (-1).
			return new int[]{Integer.MIN_VALUE, -1};
		}

		// Get the interval of the current Node
		int minIndex = currNode.a;
		int maxIndex = currNode.b;

		//base case. requested indices are completely out of this Node's interval range.
		if (maxIndex < requestedMinIndex || minIndex > requestedMaxIndex) {
			return new int[]{Integer.MIN_VALUE, -1};
		}

		/* base case. the requested interval indices "cover" the currentNode's minIndex and maxIndex.
		 * That is, the currentNode's interval lies "inside" the requested interval.
		 * Therefore, there is no need to look at currentNode's children. Just return its stored max value. */
		if (minIndex >= requestedMinIndex && maxIndex <= requestedMaxIndex) {
			return currNode.maxValueAndStationNumber;
		}

		/* If we get this far, the requested interval is partially inside and partially outside the currentNode's interval.
		 * Thus, we need to explore the children Nodes, breaking up the interval until we can patch together a perfect fit
		 * between the requested interval and the Node's (and their children's) intervals.
		 *
		 * For example, if the requested interval is [2, 5] but the currentNode's interval is [4, 7], then we need to
		 * explore its leftChild and rightChild, where the leftChild will have interval [4, 5] and rightChild will have
		 * interval [6, 7]. Then, leftChild will return its max. value in its interval, and rightChild will return its max.
		 * value in its interval...except that in this case, rightChild's interval is COMPLETELY outside of the
		 * requested interval's range, so rightChild will return {Integer.MIN_VALUE, -1}.
		 * Afterwards, the max. Values returned from left and right child will be compared and the max. will be taken.
		 *
		 * Another example: requested interval is [3, 4] and currentNode's interval is [1, 6]. Then break it up:
		 * leftChild with interval [1, 3] -> break up again -> leftleftChild [1,2], leftrightChild [3,3]
		 * rightChild with interval [4, 6] -> break up again -> rightleftChild [4,5], rightrightChild [6,6]
		 * leftleftChild's interval is OUT OF RANGE.
		 * leftrightChild's interval is "covered" by requested interval -> return that leaf Node's value.
		 * rightrightChild's interval [6,6] is OUT OF RANGE.
		 * rightleftChild must be broken up again -> eventually, only rightleftleftChild's interval [4,4] is within requested range,
		 * and its value will be returned.
		 *
		 * So, eventually, rightleftleftChild's value will be compared with leftrightChild's value and whichever is larger
		 * will be returned. */
		int[] maxQueryFromLeft = maxQuery(requestedMinIndex, requestedMaxIndex, currNode.left);
		int[] maxQueryFromRight = maxQuery(requestedMinIndex, requestedMaxIndex, currNode.right);
		if (maxQueryFromLeft[0] > maxQueryFromRight[0]) {
			return maxQueryFromLeft;
		} else {
			return maxQueryFromRight;
		}
	}
	//end private int maxQuery
}