407B - Long Path - CodeForces Solution

#include <bits/stdc++.h>
#include <algorithm>


#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
 
typedef long long int ll;
using namespace std;
 
 
ll mydiv(ll a, ll b){
    if( a % b == 0)
        return a / b;
    else
        return (a / b) + 1;
}
 
long long gcd(long long int a, long long int b)
{
  if (b == 0)
    return a;
  return gcd(b, a % b);
}
 
// Function to return LCM of two numbers
long long lcm(ll a, ll b)
{
    return (a / gcd(a, b)) * b;
}

void solve(){
    
    ll n, m = 1000000007;
    cin>>n;
    
    vector <ll> v(n + 1), dp(n + 1);
    
    for(ll i = 1; i <= n; i++)
        cin>>v[i];
    
    dp[0] = 0;
    
    for(ll i = 1; i <= n; i++){
        if(v[i] == i)
            dp[i] = (dp[i - 1] + 2) % m;
        else{
            if(dp[i - 1] <= dp[v[i] - 1])
                dp[i] = ((dp[i - 1] + 2) % m + (m + dp[i - 1] - dp[v[i] - 1]) % m) % m;
            else
                dp[i] = ((dp[i - 1] + 2) % m + (dp[i - 1] - dp[v[i] - 1]) % m) % m;
        }
    }
    cout<<dp[n];
}

int main(){
    
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
    solve();
	
	return 0;
}