#include "books.h"
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 1e6 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, s, val[maxn], nxt, L[maxn], R[maxn];
vector<vector<int> > edge;
vector<int>p;
vector<pair<int, pii> > edges;
ll ans;
int par[maxn];
int root(int v)
{
return v == par[v] ? v : par[v] = root(par[v]);
}
bool unite(int a, int b)
{
a = root(a), b = root(b);
if(a == b)
return false;
par[b] = a;
return true;
}
void clr()
{
for(int i = 0; i < maxn; i++)
{
L[i] = mod;
R[i] = -mod;
}
ans = 0;
nxt = 0;
edges.clear();
memset(val, 0, sizeof val);
}
ll minimum_walk(vector<int>perm, int S)
{
clr();
s = S;
p = perm;
n = sz(p);
set<int>one;
for(int i = 0; i < n; i++)
{
if(!val[i])
{
int col = ++nxt, cur = i, cnt = 0, chk = 0;
while(!val[cur])
{
//cout << "-- " << cur << " " << col << endl;
L[col] = min(L[col], cur);
R[col] = max(R[col], cur);
if(cur == s)
chk = 1;
cnt++;
val[cur] = col;
ans += abs(p[cur] - cur);
cur = p[cur];
}
if(cnt == 1 && !chk)
one.insert(col);
}
}
vector<int>belong[nxt + 1];
for(int i = 0; i < n; i++)
belong[val[i]].pb(i);
edge = vector<vector<int> > (n, vector<int>(n, mod));
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
if(val[i] != val[j])
edge[val[i]][val[j]] = min(edge[val[i]][val[j]], j - i);
}
}
for(int i = 1; i <= nxt; i++)
{
//cout << i << " " << L[i] << " " << R[i] << endl;
for(int j = 1; j <= nxt; j++)
{
if(i == j)
continue;
for(int a : belong[i])
{
for(int b : belong[j])
{
if((a < b && p[a] > b) || (a > b && p[a] < b))
edge[i][j] = edge[j][i] = 0;
}
//if((a < L[j] && p[a] > R[j]) || (a > R[j] && p[a] < L[j]))
//edge[i][j] = edge[j][i] = 0;
}
}
}
for(int i = 1; i <= nxt; i++)
par[i] = i;
for(int i = 1; i <= nxt; i++)
for(int j = i + 1; j <= nxt; j++)
edges.pb({edge[i][j], {i, j}});
sort(all(edges));
for(auto aa : edges)
{
if(one.count(aa.y.x) || one.count(aa.y.y))
continue;
if(unite(aa.y.x, aa.y.y))
ans += aa.x * 2;
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false), cin.tie(0);
vector<int>perm;
for(int i = 0; i < 4; i++)
perm.pb(i);
do
{
for(int i = 0; i < 4; i++)
{
clr();
cout << "permutaiton ";
for(int a : perm)
cout << a << " ";
cout << endl;
cout << "start: " << i << " " << minimum_walk(perm, i) << endl;
}
} while(next_permutation(all(perm)));
ifstream fin("in.txt");
int n, s;
fin >> n >> s;
perm.resize(n);
for(int i = 0; i < n; i++)
fin >> perm[i];
cout << minimum_walk(perm, s) << endl;
cout << minimum_walk({3, 2, 1, 0}, 0);
return 0;
}*/
