#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
map<pair<vi,int>,int> dist;
queue<pair<vi,int> > q;
void relax(vi &p, int s, int v)
{
if(dist.find(mp(p,s))==dist.end())
{
dist[mp(p,s)]=v+1; q.push(mp(p,s));
}
}
void gen_brute(int n, int s)
{
vi ori;
for(int i=0;i<n;i++) ori.pb(i+1);
dist.clear();
dist[mp(ori,s)]=0; q.push(mp(ori,s));
while(!q.empty())
{
vi curv=q.front().fi; int curs=q.front().se; int d=dist[mp(curv,curs)]; q.pop();
if(curs>0) relax(curv,curs-1,d);
if(curs+1<n) relax(curv,curs+1,d);
int curhold=0; int B=0;
for(int i=0;i<n;i++)
{
if(curv[i]>0) B^=(1<<(curv[i]-1));
}
if(B==(1<<n)-1)
{
curhold=curv[curs]-1; curv[curs]=0;
relax(curv,curs,d-1);
curv[curs]=curhold+1;
}
else
{
curhold=31-__builtin_clz(((1<<n)-1)^B);
curv[curs]=curhold+1;
relax(curv,curs,d-1);
curv[curs]=0;
}
}
}
int get_naive(vi p, int s)
{
for(int i=0;i<p.size();i++) p[i]++;
return dist[mp(p,s)];
}
bool vis[1001111];
int sum[1001111];
vector<vi> cycles;
int D[1001111];
int getdist(int s, int e) //get distance from cycle s to cycle e
{
int l=cycles[s].front(); int r=cycles[s].back();
int lb=lower_bound(cycles[e].begin(),cycles[e].end(),l)-cycles[e].begin();
if(lb<cycles[e].size()&&cycles[e][lb]<=r) return 0;
int mndist = int(1e9);
if(lb<cycles[e].size()) mndist=min(mndist,cycles[e][lb]-r);
lb--;
if(lb>=0) mndist=min(mndist,l-cycles[e][lb]);
//cerr<<"GET DIST "<<s<<' '<<e<<' '<<mndist<<'\n';
return mndist;
}
ll solve(vi p, int s)
{
//solve for s=0
int n=p.size();
for(int i=0;i<n;i++) vis[i]=0;
cycles.clear();
cycles.pb({s});
int excross=0;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
vi cycle;
vis[i]=1; cycle.pb(i);
int cur=p[i];
while(!vis[cur])
{
cycle.pb(cur); vis[cur]=1; cur=p[cur];
}
sort(cycle.begin(),cycle.end());
if(cycle.size()>=2)
{
if(cycle[0]<=s&&cycle.back()>=s) excross=1;
cycles.pb(cycle);
}
}
}
int mxans=0;
ll ans=0;
for(int i=0;i<n;i++) ans+=abs(p[i]-i);
priority_queue<ii,vector<ii>,greater<ii> > pq;
for(int i=0;i<cycles.size();i++) D[i]=int(1e9);
pq.push(mp(0,0)); D[0]=0;
while(!pq.empty())
{
int d=pq.top().fi; int u=pq.top().se; pq.pop();
if(d>D[u]) continue;
mxans=max(mxans,d);
for(int i=0;i<cycles.size();i++)
{
if(i==u) continue;
int getd=getdist(u,i);
if(d+getd<D[i])
{
D[i]=d+getd;
pq.push(mp(d+getd,i));
}
}
}
if(!excross)
{
int a[2]={0,0};
for(int i=1;i<cycles.size();i++)
{
if(cycles[i][0]<s) a[0]=max(a[0],D[i]);
else a[1]=max(a[1],D[i]);
}
mxans=a[0]+a[1];
}
return ans+2*mxans;
}
void test(int n, int s)
{
vi p;
for(int i=0;i<n;i++) p.pb(i);
gen_brute(n,s);
do
{
for(int v:p)
{
cerr<<v<<' ';
}
cerr<<'\n';
int sum=0;
for(int i=0;i<p.size();i++) sum+=abs(i-p[i]);
int ans=get_naive(p,s);
if(ans!=solve(p,s))
{
cerr<<"WARRRRRRRRRRNING\n";
}
cerr<<ans<<' '<<solve(p,s)<<' '<<ans-sum<<'\n';
}while(next_permutation(p.begin(),p.end()));
}
long long minimum_walk(std::vector<int> p, int s)
{
int n=p.size();
//test(n,s);
return solve(p,s);
}
