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.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
 public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 1000000007;
    long fac[]= new long[1000001];
    long inv[]=new long[1000001];
    public  void solve() throws IOException 
    {

       int n = readInt();

       int  arr[]=new int[n+1];

       for(int i=1;i<n;i++)
       {
         arr[i]= readInt();
       }
       
       long dp[]=new long[n+1];

       dp[n-1]=1;

       int seg[]=new int[4*n+8];
       build(seg,arr,1,n,0);
       for(int i=n-2;i>=1;i--)
       {
        if(arr[i]==n)
            dp[i]= n-i;
        else
        {
             int val = find(seg,1,n,0,i+1,(int)arr[i],arr);
            
             dp[i]= dp[val];
             dp[i]= dp[i]+n-i-arr[i]+val;
        }
       }

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

       out.println(ans);
       




       


    }
    public int find(int seg[] , int left , int right, int index, int l , int r, int arr[])
    {      
        
            

             if(left>right||left>r||l>right)
                return 0;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val1= find(seg, left,mid,2*index+1,l,r,arr);
            int val2 = find(seg,mid+1,right,2*index+2,l,r,arr);
            if(val2==0)
                return val1;
            if(val1==0)
                return val2;
            if(arr[val1]>=arr[val2])
                return val1;
            else
                return val2;


    }

    public int build( int seg[], int arr[], int left , int right , int index)
    {

              if(left==right)
              {
                seg[index]=left;
                return seg[index];
              }

              int mid = left+(right-left)/2;

              int val1 = build(seg,arr,left,mid,2*index+1);
              int val2 = build(seg,arr,mid+1,right,2*index+2);

              if(arr[val1]>=arr[val2])
                seg[index]=val1;
              else
                seg[index]=val2;
             
              return seg[index];

     }
    
    
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int u ;
    int v;
    
    edge(int u, int v)
    {
       this.u=u;
       this.v=v;
    }
    public int compareTo(edge e)
    {
        return this.v-e.v;
    }
}