// ItnoE
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000006;
int n, M[N], A[N], MN[N * 2], MX[N * 2];
inline void Set(int i, int val)
{
i += n;
MN[i] = MX[i] = val;
for (; i; i >>= 1)
{
MN[i >> 1] = min(MN[i], MN[i ^ 1]);
MX[i >> 1] = max(MX[i], MX[i ^ 1]);
}
}
inline pair < int , int > Get(int l, int r)
{
r ++;
l += n; r += n;
pair < int , int > ret = {INT_MAX, INT_MIN};
for (; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
{
ret.first = min(ret.first, MN[l]);
ret.second = max(ret.second, MX[l]);
l ++;
}
if (r & 1)
{
r --;
ret.first = min(ret.first, MN[r]);
ret.second = max(ret.second, MX[r]);
}
}
return (ret);
}
int64_t minimum_walk(vector < int > P, int st)
{
n = (int)P.size();
ll SM = 0;
for (int i = 0; i < n; i ++)
SM += abs(P[i] - i), Set(i, P[i]);
vector < pair < int , int > > cyc;
for (int i = 0; i < n; i ++)
if (!M[i] && P[i] != i)
{
int v = i;
int Mx = -N * 2, Mn = N * 2;
while (!M[v])
{
M[v] = 1;
Mn = min(Mn, v);
Mx = max(Mx, v);
v = P[v];
}
A[Mn] = max(A[Mn], Mx);
cyc.push_back({Mn, Mx});
}
if (SM == 0)
return (SM);
//bool fail = 1;
int Mx = 0, last = -1;
vector < pair < int , int > > vec;
for (int i = 0; i < n; i ++)
{
Mx = max({Mx, A[i], i});
if (P[i] != i && last == -1)
last = i;
if (P[i] == i)
continue;
if (Mx == i)
vec.push_back({last, Mx}), last = -1;
//if (i <= st && st <= Mx)
//fail = 0;
}
if (P[st] == st)
{
int le = st, ri = st;
while (le >= 0 && P[le] == le)
le --;
while (ri < n && P[ri] == ri)
ri ++;
if (le == -1) le = st;
if (ri == n) ri = st;
SM += (ri - le) * 2;
}
else
{
pair < int , int > X;
for (auto Y : vec)
if (Y.first <= st && st <= Y.second)
X = Y;
int le = st, ri = st;
int tole = st, tori = st, cnt = 0;
while (le > X.first || ri < X.second && cnt <= 2000)
{
cnt ++;
while (1)
{
auto ff = Get(le, ri);
if (ff.first >= le && ff.second <= ri)
break;
le = min(ff.first, le);
ri = max(ff.second, ri);
}
tole = le;
tori = ri;
if (X.first == le && X.second == ri)
break;
while (tole >= X.first && P[tole] == tole)
tole --;
while (tori <= X.second && P[tori] == tori)
tori ++;
SM += (le - tole) * 2;
SM += (tori - ri) * 2;
le = tole;
ri = tori;
}
}
/*if (st != 0 && P[st] != st)
{
pair < int , int > X;
for (auto Y : vec)
if (Y.first <= st && st <= Y.second)
X = Y;
SM += min(st - X.first, X.second - st) * 2;
}*/
for (int i = 1; i < (int)vec.size(); i ++)
{
SM += (vec[i].first - vec[i - 1].second) * 2;
assert(vec[i].first > vec[i - 1].second);
}
return (SM);
}
