#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define INF 1000000000000000000LL
#define ff first
#define ss second
lld n;
lld comps;
lld cyc[1000100];
vector<vector<lld>> cycles;
pair<pair<lld,lld>,pair<lld,lld>> reach[1000100];
lld lfinal, rfinal;
void debug(){
for(lld i=0;i<n;i++) cout << cyc[i] << " \n"[i==n-1];
for(lld i=0;i<comps;i++)
if((lld)cycles[i].size()>1) cout << i << ": " << reach[i].ff.ff << " " << reach[i].ff.ss << " " << reach[i].ss.ff << " " << reach[i].ss.ss << "\n";
}
lld minimum_walk(vector<int> p, int s){
n = (lld) p.size();
lld ans = 0;
for(lld i=0;i<n;i++) ans+=abs(p[i]-i);
vector<bool> vis(n, false);
comps = 0;
lfinal = INF, rfinal = -1;
for(lld i=0;i<n;i++){
if(!vis[i]){
vector<lld> tmp;
lld x = i;
while(true){
if(vis[x]) break;
tmp.push_back(x);
vis[x] = true;
cyc[x] = comps;
x = p[x];
}
sort(tmp.begin(), tmp.end());
cycles.push_back(tmp);
if((int)tmp.size()>1){
if(tmp.front()>=s) reach[comps] = {{tmp.front(),-1},{tmp.front(),tmp.back()}};
else if(tmp.back()<=s) reach[comps] = {{tmp.front(),tmp.back()},{INF,tmp.back()}};
else{
auto it = lower_bound(tmp.begin(), tmp.end(), s);
reach[comps] = {{tmp.front(),*prev(it)},{*it,tmp.back()}};
}
lfinal = min(lfinal, reach[comps].ff.ff);
rfinal = max(rfinal, reach[comps].ss.ss);
}else{
reach[comps] = {{tmp[0],tmp[0]},{tmp[0],tmp[0]}};
}
comps++;
}
}
lld cur_comp = cyc[s];
lld lblock = s, rblock = s;
lld lblocknew = reach[cur_comp].ff.ff, rblocknew = reach[cur_comp].ss.ss;
while(lblocknew!=lblock||rblocknew!=rblock){
lld lblocknewnew, rblocknewnew;
for(lld i=lblocknew;i<=lblock;i++){
if((lld)cycles[cyc[i]].size()==1) continue;
reach[cur_comp].ff.ff = min(reach[cur_comp].ff.ff, reach[cyc[i]].ff.ff);
reach[cur_comp].ff.ss = max(reach[cur_comp].ff.ss, reach[cyc[i]].ff.ss);
reach[cur_comp].ss.ff = min(reach[cur_comp].ss.ff, reach[cyc[i]].ss.ff);
reach[cur_comp].ss.ss = max(reach[cur_comp].ss.ss, reach[cyc[i]].ss.ss);
lblocknewnew = reach[cur_comp].ff.ff;
rblocknewnew = reach[cur_comp].ss.ss;
cyc[i] = cur_comp;
}
for(lld i=rblock;i<=rblocknew;i++){
if((lld)cycles[cyc[i]].size()==1) continue;
reach[cur_comp].ff.ff = min(reach[cur_comp].ff.ff, reach[cyc[i]].ff.ff);
reach[cur_comp].ff.ss = max(reach[cur_comp].ff.ss, reach[cyc[i]].ff.ss);
reach[cur_comp].ss.ff = min(reach[cur_comp].ss.ff, reach[cyc[i]].ss.ff);
reach[cur_comp].ss.ss = max(reach[cur_comp].ss.ss, reach[cyc[i]].ss.ss);
lblocknewnew = reach[cur_comp].ff.ff;
rblocknewnew = reach[cur_comp].ss.ss;
cyc[i] = cur_comp;
}
lblock = lblocknew; rblock = rblocknew;
lblocknew = lblocknewnew; rblocknew = rblocknewnew;
}
lld l = INF;
for(lld i=lblock-1;i>=lfinal;i--){
if((lld)cycles[cyc[i]].size()==1) continue;
if(i<l){
cur_comp = cyc[i];
l = reach[cur_comp].ff.ff;
}else{
reach[cur_comp].ff.ff = min(reach[cur_comp].ff.ff, reach[cyc[i]].ff.ff);
reach[cur_comp].ff.ss = max(reach[cur_comp].ff.ss, reach[cyc[i]].ff.ss);
reach[cur_comp].ss.ff = min(reach[cur_comp].ss.ff, reach[cyc[i]].ss.ff);
reach[cur_comp].ss.ss = max(reach[cur_comp].ss.ss, reach[cyc[i]].ss.ss);
l = reach[cur_comp].ff.ff;
cyc[i] = cur_comp;
}
}
lld r = -1;
for(lld i=rblock+1;i<=rfinal;i++){
if((lld)cycles[cyc[i]].size()==1) continue;
if(i>r){
cur_comp = cyc[i];
r = reach[cur_comp].ss.ss;
}else{
reach[cur_comp].ff.ff = min(reach[cur_comp].ff.ff, reach[cyc[i]].ff.ff);
reach[cur_comp].ff.ss = max(reach[cur_comp].ff.ss, reach[cyc[i]].ff.ss);
reach[cur_comp].ss.ff = min(reach[cur_comp].ss.ff, reach[cyc[i]].ss.ff);
reach[cur_comp].ss.ss = max(reach[cur_comp].ss.ss, reach[cyc[i]].ss.ss);
r = reach[cur_comp].ss.ss;
cyc[i] = cur_comp;
}
}
//debug();
l = lblock, r = rblock;
while(l>lfinal||r<rfinal){
lld i, j;
lld lpath = (l-1<lfinal?INF:0), rpath = (r+1>rfinal?INF:0);
for(i=l-1;i>=lfinal;i--){
if(reach[cyc[i]].ff.ff<s&&reach[cyc[i]].ss.ss>s){
lpath+=2;
break;
}
if(cyc[i]!=cyc[i+1]) lpath+=2;
i = reach[cyc[i]].ff.ff;
if(i==lfinal) break;
}
for(j=r+1;j<=rfinal;j++){
if(reach[cyc[j]].ff.ff<s&&reach[cyc[j]].ss.ss>s){
rpath+=2;
break;
}
if(cyc[j]!=cyc[j-1]) rpath+=2;
j = reach[cyc[j]].ss.ss;
if(j==rfinal) break;
}
ans += min(lpath, rpath);
l = reach[cyc[i]].ff.ff;
r = reach[cyc[j]].ss.ss;
}
return ans;
}
