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.BufferedInputStream;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;

public class P675E {

    private static class AI implements Comparable<AI> {
        public final int a;
        public final int i;

        public AI(int a, int i) {
            this.a = a;
            this.i = i;
        }

        @Override
        public int compareTo(AI other) {
            int c = Integer.compare(this.a, other.a);
            if (c == 0) {
                c = Integer.compare(this.i, other.i);
            }
            return c;
        }

        public static AI max(AI ai1, AI ai2) {
            return (ai1.compareTo(ai2) >= 0) ? ai1 : ai2;
        }

        @Override
        public boolean equals(Object other) {
            if (other == this) {
                return true;
            }
            if (!(other instanceof AI)) {
                return false;
            }
            final AI that = (AI) other;
            return this.a == that.a && this.i == that.i;
        }
    }

    private static class STNode {
        public final int i;
        public final int j;
        public final int k;
        public final STNode left;
        public final STNode right;
        public final AI m;

        public STNode(int i, int j, int[] A) {
            this.i = i;
            this.j = j;
            this.k = (i + j) / 2;
            if (j == i+1) {
                this.left = null;
                this.right = null;
                this.m = new AI(A[i], i);
            } else {
                this.left = new STNode(i, k, A);
                this.right = new STNode(k, j, A);
                this.m = AI.max(left.m, right.m);
            }
        }

        public AI get(int i0, int j0) {
            if (i0 <= i && j <= j0) {
                return this.m;
            } else if (j0 <= k) {
                return this.left.get(i0, j0);
            } else if (k <= i0) {
                return this.right.get(i0, j0);
            } else {
                return AI.max(this.left.get(i0, j0), this.right.get(i0, j0));
            }
        }
    }

    private static long trains(final int n, final int[] A) {
        final STNode st = new STNode(0, n-1, A);
        final long[] P = new long[n];
        P[n-2] = 1;
        // P[i] = (A[i] - i) + (n - 1 - j) + P[j] - 2 * (A[i] - j)
        for (int i = n-2; i >= 0; i--) {
            if (A[i] == n-1) {
                P[i] = A[i] - i;
                continue;
            }
            final int j = st.get(i+1, A[i]+1).i;
            P[i] = j - i + P[j] + n - 1 - A[i];
        }

        long s = 0;
        for (final long p : P) {
            s += p;
        }
        return s;
    }

    public static void main(String[] args) throws IOException {
        try {
            final FastReader fr = new FastReader(
                new BufferedInputStream(System.in));
            final int n = fr.readInt();
            final int[] A = new int[n-1];
            for (int i = 0; i < n-1; i++) {
                A[i] = fr.readInt() - 1;
            }
            System.out.println(trains(n, A));
        } catch (Throwable t) {
            t.printStackTrace(System.out);
            System.exit(1);
        }
    }

    private static final void log(Object o) {
        System.err.println(o);
    }

    private static class FastReader implements Closeable {
        private static final byte B_SP = ' ';
        private static final byte B_CR = '\r';
        private static final byte B_LF = '\n';
        private static final byte B_0 = '0';
        private static final byte B_9 = '9';
        private static final byte B_DASH = '-';

        private final InputStream in;
        private byte prev;

        public FastReader(InputStream in) {
            this.in = in;
        }

        public byte read() throws IOException {
            return (prev = (byte) in.read());
        }

        public byte readNonWs() throws IOException {
            byte b;
            do {
                b = read();
            } while (b <= B_SP);
            return b;
        }

        public int readInt() throws IOException {
            byte b = readNonWs();
            final boolean neg = (b == B_DASH);
            if (neg) {
                b = read();
            }
            int i = (b - B_0);
            b = read();
            while (b >= B_0 && b <= B_9) {
                i = i * 10 + (b - B_0);
                b = read();
            }
            return neg ? -i : i;
        }

        public long readLong() throws IOException {
            byte b = readNonWs();
            final boolean neg = (b == B_DASH);
            if (neg) {
                b = read();
            }
            long i = (b - B_0);
            b = read();
            while (b >= B_0 && b <= B_9) {
                i = i * 10 + (b - B_0);
                b = read();
            }
            return neg ? -i : i;
        }

        public int readToken(byte[] tbuf) throws IOException {
            byte b = readNonWs();
            int i = 0;
            do {
                tbuf[i++] = b;
                b = read();
            } while (b >= B_SP);
            return i;
        }

        public int readLine(byte[] lbuf) throws IOException {
            byte b;
            if (prev == B_CR) {
                b = read();
                if (b == B_LF) {
                    b = read();
                }
            } else {
                b = read();
            }
            int i = 0;
            while (b >= B_SP) {
                lbuf[i++] = b;
                b = read();
            }
            return i;
        }

        @Override
        public void close() throws IOException {
            in.close();
        }
    }

}
