#include "books.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 1e6+10;
const int MAXA = 2e5+10;
const int SQRT = 450;
const ll INF = 2e12;
const int MOD = 1e9+7;
const int LOG = 30;
int sum(int a, int b){
ll te = a+MOD+b;
for(; te >= MOD; ) te -= MOD;
return (int)te;
}
void chsum(int &a, int b){ a = sum(a,b); }
int mul(int a, int b){
a%=MOD; b%=MOD; ll te = 1ll*a*b%MOD; return (int)(te);
}
void chmul(int &a, int b){ a = mul(a,b); }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
ll ans, n, done[MAXN];
vector<array<ll,3>> seg;
long long minimum_walk(std::vector<int> p, int s) {
n = p.size();
for(int i=0; i<n; i++){
if(done[i] || p[i] == i) continue;
ll nw = i, tot = 0, mn = i, mx = i;
while(!done[nw]){
done[nw] = 1;
tot += abs(nw-p[nw]);
nw = p[nw];
chmx(mx, nw);
}
// cout << mn << ' '<< mx << ' '<< tot/2 << " tot\n";
seg.pb({mn, mx, tot/2});
}
sort(seg.begin(), seg.end());
ll mx = 0;
for(int i=0; i<seg.size(); ){
int j = i;
ll all = 0, le = seg[i][0], ri = seg[i][1];
while(i<seg.size()){
if(ri < seg[i][0]){
break;
}
all += seg[i][2];
chmx(ri, seg[i][1]);
i++;
}
chmx(mx, ri);
ans += all-(ri-le);
// cout << all << ' '<< le << ' '<< ri << " leri\n";
}
ans += mx;
return 2*ans;
}
