#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const ll inf = 1e18;
ll used[maxn];
int lb[maxn], rb[maxn], n;
int bef[maxn], aft[maxn];
vector < int > st[maxn];
int l, r, cnt;
void extend(int left, int right)
{
while(l > left || r < right)
{
if (l > left)
{
l --;
if (used[l] != 0)
{
left = min(left, lb[used[l]]);
right = max(right, rb[used[l]]);
}
}
if (r < right)
{
r ++;
if (used[r] != 0)
{
left = min(left, lb[used[r]]);
right = max(right, rb[used[r]]);
}
}
}
}
ll left_cost(int to)
{
int gt = l, cost = 0;
for (int i = l - 1; i >= to; i --)
{
if (used[i] == 0)
continue;
if (gt > i)
cost = cost + (gt - i) * 2;
gt = min(gt, lb[used[i]]);
}
return cost;
}
ll right_cost(int to)
{
int gt = r, cost = 0;
for (int i = r + 1; i <= to; i ++)
{
if (used[i] == 0)
continue;
if (gt < i)
cost = cost + (i - gt) * 2;
gt = max(gt, rb[used[i]]);
}
return cost;
}
long long minimum_walk(vector<int> p, int s)
{
n = p.size();
int cnt = 0;
ll ans = 0;
for (int i = 0; i < n; i ++)
{
ans = ans + abs(p[i] - i);
if (p[i] == i)
continue;
if (used[i])
continue;
cnt ++;
used[i] = cnt;
int v = p[i];
lb[cnt] = i;
rb[cnt] = i;
st[cnt].push_back(i);
while(v != i)
{
st[cnt].push_back(v);
used[v] = cnt;
rb[cnt] = max(rb[cnt], v);
v = p[v];
}
}
l = s + 1;
r = s;
extend(s, s);
while(true)
{
///cout << l << " " << r << " " << ans << endl;
int bf = l - 1, af = r + 1;
while(bf >= 0)
{
if (used[bf] == 0)
{
bf --;
continue;
}
if (lb[used[bf]] < l && rb[used[bf]] > r)
break;
bf --;
}
while(af < n)
{
if (used[af] == 0)
{
af ++;
continue;
}
if (lb[used[af]] < l && rb[used[af]] > r)
break;
af ++;
}
if (bf != -1)
{
ll lc = left_cost(bf);
ll rc = right_cost(af);
ans = ans + min(lc, rc);
extend(bf, af);
}
else
{
ll lc = left_cost(0);
ll rc = right_cost(n - 1);
///scout << lc << " " << rc << endl;
ans = ans + lc + rc;
break;
}
}
///cout << dp[lf][rf] << endl;
///cout << lf << " " << rf << endl;
return ans;
}
