#include "books.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
ll i,w;
bool operator<(const obj &o)const{
return w>o.w;
}
};
struct BIT{
ll n;
vector<ll> a;
BIT(ll N):n(N),a(N+5,0){}
void add(ll i, ll v){
for(;i<=n;i+=i&-i) a[i] += v;
}
ll get(ll i){
ll v = 0;
for(;i>0;i-=i&-i) v += a[i];
return v;
}
};
long long minimum_walk(std::vector<int> p, int s) {
ll ans = 0;
ll n = p.size();
/*
if (s == 0){
vector<ll> u(n,0);
for(ll i = 0;i<n;i++){
if(p[i]!=i){
ans += i-s;
s = i;
ll x = i;
do{
ans += abs(p[x]-x);
ll y = x;
x = p[x];
p[y] = y;
} while(x!=i);
}
}
ans += s;
}*/
ll gpc = 0;
vector<ll> gp(n,-1);
vector<ll> L,R;
vector<vector<ll>> gps;
for(ll i = 0;i<n;i++){
if (gp[i]==-1){
ll cur = gpc++;
gps.emplace_back();
L.push_back(n);
R.push_back(0);
ll x = i;
do{
L[cur] = min(x,L[cur]);
R[cur] = max(x,R[cur]);
gp[x] = cur;
gps[cur].push_back(x);
ans += abs(p[x]-x);
x = p[x];
} while(x!=i);
}
}/*
for(ll i = 0;i<gpc;i++){
cout << L[i] << "~" << R[i] << " " << gps[i].size() << endl;
}*/
/*
vector<ll> cost(n,n);
priority_queue<obj> q;
q.push({s,0});
vector<ll> vis(gpc,0);
BIT t(n+5);
while(!q.empty()){
auto [i,w] = q.top();q.pop();
if(t.get(i+1)) w = 0;
if (cost[i]<=w) continue;
cost[i] = w;
ll l = n,r = 0;
if (!vis[gp[i]]){
vis[gp[i]] = 1;
if (gps[gp[i]].size()>1) ans += cost[i]*2;
for(ll j : gps[gp[i]]){
q.push({j,0});
}
l = L[gp[i]];
r = R[gp[i]];
t.add(l+1,1);
t.add(r+2,-1);
}
//cerr << i << " " << w << " " << l << " " << r << endl;
if(i>0) q.push({i-1,w+1});
if(i<n-1) q.push({i+1,w+1});
}*/
vector<ll> v(n,0);
for(ll i : L) v[i]++;
for(ll i : R) v[i]--;
for(ll i = 1;i<n;i++) v[i] += v[i-1];
ll rf = n-1;
while(rf&&p[rf]==rf) rf--;
for(ll i = 0;i<rf;i++) if(!v[i]) ans += 2;
return ans;
}
