#include "books.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define ii pair<int, int>
#define x first
#define y second
#define vii vector<ii>
#define pb push_back
#define all(x) x.begin(), x.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;
const int INF = 1e9;
typedef long long ll;
struct DSU{
int n;
vi p, sz;
DSU(int n):n(n), p(n,-1), sz(n,1){}
int find(int c){
if (p[c]==-1) return c;
return p[c] = find(p[c]);
}
void uni(int a, int b){
a = find(a), b = find(b);
if (a==b) return ;
if (sz[a]>sz[b]) swap(a,b);
p[a] = b;
sz[b] += sz[a];
}
};
ll minimum_walk(vi p, int s) {
ll ans = 0;
int n = p.size();
vb check(n,0);
int needl = s, needr = s;
vi v1(n), v2(n);
loop(i,0,n) if(!check[i]){
vi vec;
int mn = i, mx = i;
for(int cur = i;!check[cur]; cur = p[cur]){
check[cur] = 1;
ans+=abs(cur-p[cur]);
vec.pb(cur);
chkmin(mn, cur); chkmax(mx, cur);
}
if (vec.size()>1) chkmax(needr, mx), chkmin(needl, mn);
for(auto x:vec) v2[x] = mx, v1[x] = mn;
}
int l = s, r = s, ml=s, mr=s;
while(l>=ml || r<=mr){
if (l>=ml){
chkmax(mr, v2[l]);
chkmin(ml, v1[l]);
l--;
}
else{
chkmax(mr, v2[r]);
chkmin(ml, v1[r]);
r++;
}
}
vi right(1,l+1), left(1,r-1);
vi comp(n,0); int cnt = 0;
while(r<n){
if (r>mr) right.pb(n), mr++, cnt++;
comp[r] = cnt;
chkmax(mr, v2[r]);
chkmin(right.back(), v1[r]);
r++;
}
cnt = 0;
while(l>=0){
if (l<ml) left.pb(-1), ml--, cnt++;
comp[l] = cnt;
chkmin(ml, v1[l]);
chkmax(left.back(), v2[l]);
l--;
}
int a = left.size(), b = right.size();
for(int &x:left) x = comp[x] + (x>s?a:0);
for(int &x:right) x = comp[x] + (x>s?a:0);
needl = comp[needl], needr = comp[needr];
DSU dsu(a+b);
dsu.uni(0,a); //same one
loop(i,0,a) dsu.uni(i, left[i]);
loop(i,0,b) dsu.uni(i+a, right[i]);
map<int, int> conv; int tmp=0;
loop(i,0,a+b) if(dsu.p[i]==-1) conv[i]=tmp++;
vvi g(tmp);
auto get = [&](int i){
return conv[dsu.find(i)];
};
loop(i,0,a-1){
int aa = get(i), bb = get(i+1);
if (aa!=bb) g[aa].pb(bb);
}
loop(i,0,b-1){
int aa = get(i+a), bb = get(i+a+1);
if (aa!=bb) g[aa].pb(bb);
}
vi vals(tmp);
loop(i,0,a) vals[get(i)]|=1;
loop(i,0,b) vals[get(i+a)]|=2;
//one that has 3 is both
needl = get(needl), needr = get(needr+a); //updating targets
queue<int> q; q.push(get(0));
vi dist(tmp,-1); dist[get(0)] = 0;
int has = 0, lasty = 0, lasth=0;
//cout<<"AB: "<<a<<" "<<b<<" "<<ans<<endl;
while(q.size()){
int cur = q.front(); q.pop();
if (vals[cur]==3) lasty = dist[cur];
if (cur==needl) ans+=2*dist[cur], has|=1;
if (cur==needr) ans+=2*dist[cur], has|=2;
//cout<<"CUR: "<<cur<<" "<<dist[cur]<<endl;
if (has!=0 && lasth==0){
ans-=2*lasty;
}
if (has==3) break;
lasth = has;
for(auto nei:g[cur]) if(dist[nei]==-1){
dist[nei]=dist[cur]+1;
q.push(nei);
}
}
return ans;
}
/*
clear
g++ books.cpp grader.cpp -o a ; ./a
4 0
0 2 3 1
11 2
10 5 2 4 3 8 7 6 1 9 0
4 1 3 2 7 6 5 0
*/
