#include "books.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define fst first
#define snd second
#define FOR(i, l, r) for(int i = l; i < r; i++)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
const ll NMAX = 1e6 + 10;
const ll INF = 1e9;
vi cycles[NMAX];
ll numCycles, N, S;
vi vis;
vi point;
void flood(ll n, ll c){
//cout << "Flood " << n << " " << c << endl;
cycles[c].pb(n);
ll k = point[n];
vis[n] = c;
if(vis[k] == -1) flood(k, c);
}
ii bounds[NMAX];
//
/*ii bounds(ll p, ll c){
//cout << p << endl;
auto &cy = cycles[c];
if(cy[0] > p) return {-1, cy[0]};
if(cy.back() <= p) return {cy.back(), INF};
auto x = lower_bound(cycles[c].begin(), cycles[c].end(), p);
return {*x, *(++x)};
}*/
ll f(ll lbound, ll rbound){
rbound --;
ii &k = bounds[vis[lbound]];
ll lgoal = k.fst, rgoal = k.snd;
//cout << lgoal << " " << rgoal << endl;
ll l = lbound, r = rbound;
while(l < lgoal || r > rgoal){
//cout << l << " " << r << endl;
ll t;
if(l >= lgoal) t = r--;
else t = l++;
ii &k = bounds[vis[t]];
lgoal = max(lgoal, k.fst);
rgoal = min(rgoal, k.snd);
}
//cout << lgoal << " " << rgoal << endl;
if(lgoal == S) return 0;
ll li = S, ri = S+1;
ll lm = lgoal, rm = lgoal;
ll c1 = 0;
FOR(i, lgoal+1, S+1){
ll a = cycles[vis[i]][0], b = cycles[vis[i]].back()+1;
if(a != i) continue;
if(b >= S) {
li = i;
break;
}
if(rm <= i){
if(rm - lm > 1) c1 += lm - rm;
lm = i;
}
rm = max(rm, b);
}
c1 += li - lgoal;
// closed interval
lm = rgoal-1; rm = rgoal-1;
ll c2 = 0;
for(int i = rgoal-1; i > S; i--){
ll a = cycles[vis[i]][0], b = cycles[vis[i]].back();
if(b != i) continue;
if(a <= S){
ri = i+1;
break;
}
if(i < lm){
if(rm - lm > 1) c2 += lm - (rm + 1);
rm = i;
}
lm = min(lm, a);
}
c2 += rgoal+1 - ri;
// Interval covering
//cout << "cover " << li << " " << ri << endl;
//cout << "c1 c2: " << c1 << " " << c2 << endl;
ll res = f(li, ri);
return res + min(c1, c2);
}
long long minimum_walk(std::vector<int> p, int s) {
vis.assign(p.size(), -1);
N = p.size();
S = s;
FOR(i, 0, N) point.pb(p[i]);
FOR(i, 0, N) if(vis[i] == -1) flood(i, numCycles++);
FOR(i, 0, numCycles) sort(cycles[i].begin(), cycles[i].end());
FOR(c, 0, numCycles) {
auto &cy = cycles[c];
if(cy[0] > s) bounds[c] = {-1, cy[0]};
else if(cy.back() <= s) bounds[c] = {cy.back(), INF};
else {
auto x = upper_bound(cycles[c].begin(), cycles[c].end(), s);
bounds[c] = {*(x-1), *(x)};
}
//cout << c << ": " << bounds[c].fst << " " << bounds[c].snd << endl;
}
//cout << "Preprocessed" << endl;
//ii k = bounds(2, 1);
//cout << k.fst << " " << k.snd << endl;
//Find segments:
vii segs;
ll rm = 0;
ll lm = 0;
ll l = -1, r = -1;
//cout << "numCycles: " << numCycles << endl;
//FOR(i, 0, numCycles) {
//for(int k : cycles[i]) cout << k << " ";
//cout << endl;
//}
FOR(i, 0, numCycles){
if(cycles[i].size() == 1) continue;
if(rm <= cycles[i][0]) {
if(rm - lm > 1) segs.pb({lm, rm});
if(lm <= S and S < rm) l = lm, r = rm;
lm = cycles[i][0]; rm = cycles[i].back()+1;
}
rm = max(rm, cycles[i].back()+1);
//cout << lm << " " << rm << " " << i << endl;
}
if(rm - lm > 1) segs.pb({lm, rm});
//cout << segs.size() << endl;
ll dist = 0;
//cout << dist << endl;
FOR(i, 0, N) dist += abs(i - p[i]);
//cout << dist << endl;
//cout << segs.size() - 1 << endl;
//FOR(i, 0, (ll)segs.size()) cout << segs[i].fst << " " << segs[i].snd << endl;
FOR(i, 0, (ll)segs.size()-1){
dist += 2*(segs[i+1].fst - (segs[i].snd-1) );
}
if(segs.size() > 0){
if(segs[0].fst > S) dist += 2 * (segs[0].fst - S);
if(segs.back().snd <= S) dist += 2*(S - segs.back().snd+1);
}
//cout << "sfdf" << endl;
if(l != -1) dist += 2*f(l, r);
return dist;
}
/*
3 1
0 2 1
4 0
0 1 3 2
4 1
2 3 0 1
4 0
0 1 2 3
10 4
0 1 4 5 2 3 7 6 9 8
10 4
0 6 4 5 2 3 7 1 9 8
10 4
0 6 2 5 4 3 7 1 9 8
10 0
0 6 2 5 4 3 7 1 9 8
*/
