#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
vector<int> dsu;
vector<int> l;
vector<int> r;
vector<int> il;
vector<int> ir;
vector<int> used;
vector<array<int, 4>> araliklar, araliklar2;
int goDSU(int a){
if (dsu[a] == a)
return a;
dsu[a] = goDSU(dsu[a]);
return dsu[a];
}
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
long long int ret = 0;
dsu.resize(n);
l.resize(n);
r.resize(n);
il.resize(n, INT_MIN);
ir.resize(n, INT_MAX);
used.resize(n);
for (int i = 0; i < n; i++){
p[i];
dsu[i] = i;
l[i] = i;
r[i] = i;
if (i <= s)
il[i] = i;
if (i >= s)
ir[i] = i;
}
for (int i = 0; i < n; i++){
ret += abs(p[i] - i);
if (goDSU(i) != goDSU(p[i])){
r[goDSU(p[i])] = max(r[goDSU(p[i])], r[goDSU(i)]);
ir[goDSU(p[i])] = min(ir[goDSU(p[i])], ir[goDSU(i)]);
l[goDSU(p[i])] = min(l[goDSU(p[i])], l[goDSU(i)]);
il[goDSU(p[i])] = max(il[goDSU(p[i])], il[goDSU(i)]);
dsu[goDSU(i)] = goDSU(p[i]);
}
}
for (int i = 0; i < n; i++){
if (!used[goDSU(i)] && l[goDSU(i)] != r[goDSU(i)]){
used[goDSU(i)] = true;
araliklar.push_back({ l[goDSU(i)], r[goDSU(i)], il[goDSU(i)], ir[goDSU(i)] });
}
}
if (araliklar.size() == 0){
return 0;
}
int mxr = araliklar[0][1];
for (int i = 1; i < araliklar.size(); i++){
if ((ir[goDSU(mxr)] == INT_MAX && araliklar[i][0] < mxr) || (il[goDSU(mxr)] == INT_MIN && araliklar[i][0] < mxr) || araliklar[i][0] < il[goDSU(mxr)] || (araliklar[i][1] > ir[goDSU(mxr)] && araliklar[i][0] < mxr)){
r[goDSU(mxr)] = max(r[goDSU(mxr)], r[goDSU(i)]);
ir[goDSU(mxr)] = min(ir[goDSU(mxr)], ir[goDSU(i)]);
l[goDSU(mxr)] = min(l[goDSU(mxr)], l[goDSU(i)]);
il[goDSU(mxr)] = max(il[goDSU(mxr)], il[goDSU(i)]);
dsu[goDSU(i)] = goDSU(mxr);
}
mxr = max(mxr, araliklar[i][1]);
}
araliklar.clear();
for (int i = 0; i < n; i++){
used[goDSU(i)] = false;
}
int jl = -1, jr = 0;
for (int i = 0; i < n; i++){
if (i == s && p[s] == s){
araliklar.push_back({ s, s, s, s });
araliklar2.push_back({ s, s, s, s });
}
if (!used[goDSU(i)] && l[goDSU(i)] != r[goDSU(i)]){
used[goDSU(i)] = true;
araliklar.push_back({ l[goDSU(i)], r[goDSU(i)], il[goDSU(i)], ir[goDSU(i)] });
araliklar2.push_back({ r[goDSU(i)], l[goDSU(i)], ir[goDSU(i)], il[goDSU(i)] });
}
}
sort(all(araliklar2));
jl = lower_bound(all(araliklar), array<int, 4>{ l[goDSU(s)], -1, -1, -1 }) - araliklar.begin();
jr = lower_bound(all(araliklar2), array<int, 4>{ r[goDSU(s)], -1, -1, -1 }) - araliklar2.begin();
while (jr < araliklar2.size() - 1 || jl > 0){
long long sum = 0, sum2 = 0;
while (jr < araliklar2.size() - 1){
sum += araliklar2[jr + 1][2] - araliklar2[jr][0];
jr++;
if (jr != araliklar2.size() && araliklar2[jr][1] < s){
break;
}
}
while (jl > 0){
sum2 += araliklar[jl][2] - araliklar[jl - 1][0];
jl--;
if (araliklar[jl][1] > s){
break;
}
}
if (jr != araliklar2.size() && araliklar2[jr][1] < s){
ret += min(sum, sum2) * 2;
sum = 0;
sum2 = 0;
}else{
ret += (sum + sum2) * 2;
}
}
return ret;
}
