#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
//#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN = 1000000;
//Global Variables
ll N, out = 0, loc[MAXN], comp[MAXN], at = 0;
/// element , element
pair<int, int> rng[MAXN];
/// comp
vector<pair<int, int> > rng2;
bool vis[MAXN];
/// element , comp
vector<int> elements[MAXN];
void go1(int at, int co) {
if (comp[at] != -1) return;
rng[co].a = min(rng[co].a, at);
rng[co].b = max(rng[co].b, at);
comp[at] = -2;
elements[co].pb(at);
out += abs(loc[at]-at);
go1(loc[at], co);
}
void go(int at) {
if (vis[at]) return;
vis[at] = true;
go(loc[at]);
}
void chg(int a, int b) {
for (int i: elements[a]) comp[i] = b;
}
ll minimum_walk(vector<int> p, int s) {
N = p.size();
ffi {rng[i] = mp(N, -1); comp[i] = -1; loc[i] = p[i];}
ffi if (comp[i] == -1) {
go1(i, at);
at++;
}
//w<< "from components: " << out<<e;
sort(rng, rng+at);
For (i, 0, at) {
/// only one element - delete
if (rng[i].a == rng[i].b) continue;
/// vector is empty
if (rng2.empty()) {
rng2.pb(rng[i]);
chg(i, 0);
continue;
}
/// fully emcompassed - delete
/// intersect - combine
if (rng[i].a < rng2.back().b && rng2.back().b < rng[i].b) {
chg(i, rng2.size()-1);
rng2.back().b = rng[i].b;
}
/// don't intersect
if (rng2.back().b < rng[i].a) {
chg(i, rng2.size());
rng2.pb(rng[i]);
}
}
at = rng2.size();
For (i, 0, at) {
rng[i] = rng2[i];
//w<< rng[i].a << " " << rng[i].b<<e;
}
bool moved = false;
int far = s;
if (comp[s] != -2) far = rng[comp[s]].b;
For (i, 0, at) if (rng[i].a > s) {
out += 2*(rng[i].a - far);
moved = true;
far = rng[i].b;
}
far = s;
if (comp[s] != -2) far = rng[comp[s]].a;
for (int i=at-1; i>=0; i--) if (rng[i].b < s) {
out += 2*(far - rng[i].b);
moved = true;
far = rng[i].a;
//w<< out<<e;
}
//w<< "moved: " << moved c out<<e;
if (moved) return out;
/// find closest location to s that isn't deleted
int dist = N+1;
ffi if (comp[i] != -2) {
dist = min(dist, abs(s-i));
}
//w<< "dist: " << dist<<e;
if (dist == N+1) dist = 0;
//w<< "dist: " << dist<<e;
return out + 2*dist;
}
