#include "books.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll comp[1000005], l[1000005], r[1000005], dist[1000005], final[1000005], visited[1000005], n, cnt;
vector<pair<ll, ll> > adj[1000005], revadj[1000005], v;
priority_queue<pair<ll, ll> > pq;
queue<ll> q;
ll minimum_walk(vector<int> a, int s)
{
ll n=a.size(), cnt=0, ans=0;
for (ll i=0; i<n; i++)
{
ans+=abs(a[i]-i);
if (comp[i] || (i!=s && a[i]==i))
continue;
cnt++;
l[cnt]=i;
ll cur=i;
while (!comp[cur])
{
comp[cur]=cnt;
r[cnt]=max(r[cnt], cur);
cur=a[cur];
}
}
ll L=1e18, R=0;
for (ll i=0; i<n; i++)
{
if (!comp[i])
continue;
L=min(L, i);
R=max(R, r[comp[i]]);
if (R==i)
{
v.push_back({L, R});
//cout << "L R " << L << ' ' << R << '\n';
L=1e18, R=0;
}
}
for (ll i=1; i<v.size(); i++)
ans+=(v[i].first-v[i-1].second)*2;
ll ind;
for (ll i=0; i<v.size(); i++)
{
if (v[i].first<=s && s<=v[i].second)
{
ind=i;
break;
}
}
//cout << "ind=" << ind << '\n';
ll pre=-1;
for (ll i=0; i<n; i++)
{
if (!comp[i])
continue;
if (pre!=-1 && comp[pre]!=comp[i])
{
if (r[comp[pre]]==pre)
{
adj[comp[pre]].push_back({comp[i], i-pre});
revadj[comp[i]].push_back({comp[pre], i-pre});
}
else
{
adj[comp[pre]].push_back({comp[i], 0});
revadj[comp[i]].push_back({comp[pre], 0});
}
}
pre=i;
}
pre=-1;
for (ll i=n-1; i>=0; i--)
{
if (!comp[i])
continue;
if (pre!=-1 && comp[pre]!=comp[i])
{
if (l[comp[pre]]==pre)
{
adj[comp[pre]].push_back({comp[i], pre-i});
revadj[comp[i]].push_back({comp[pre], pre-i});
}
else
{
adj[comp[pre]].push_back({comp[i], 0});
revadj[comp[i]].push_back({comp[pre], 0});
}
}
pre=i;
}
/*for (ll i=1; i<=cnt; i++)
{
cout << "edges: ";
for (int j=0; j<adj[i].size(); j++)
cout << adj[i][j].first << ' ' << adj[i][j].second << ' ';
cout << '\n';
}*/
for (ll i=1; i<=cnt; i++)
dist[i]=1e18;
dist[comp[s]]=0;
pq.push({0, comp[s]});
while (!pq.empty())
{
ll u=pq.top().second;
pq.pop();
if (final[u])
continue;
final[u]=1;
for (ll i=0; i<adj[u].size(); i++)
{
ll v=adj[u][i].first, w=adj[u][i].second;
if (dist[u]+w<dist[v])
{
dist[v]=dist[u]+w;
pq.push({-dist[v], v});
}
}
}
visited[comp[v[ind].first]]=1;
q.push(comp[v[ind].first]);
while (!q.empty())
{
ll u=q.front();
q.pop();
for (ll i=0; i<revadj[u].size(); i++)
{
ll v=revadj[u][i].first, w=revadj[u][i].second;
if (!w && !visited[v])
{
visited[v]=1;
q.push(v);
}
}
}
ll mn=1e18;
for (ll i=1; i<=cnt; i++)
if (visited[i])
mn=min(mn, dist[i]);
return ans+mn*2;
}
