#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];
ll solve(vi p, int s)
{
//solve for s=0
int n=p.size();
for(int i=0;i<n;i++) vis[i]=0;
vector<ii> ranges;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
int mn=i; int mx=i; vis[i]=1;
int cur=p[i];
while(!vis[cur])
{
vis[cur]=1; mn=min(mn,cur); mx=max(mx,cur); cur=p[cur];
}
if(mn<mx) ranges.pb(mp(mn,mx));
}
}
sort(ranges.begin(),ranges.end());
int mxans=0;
ll ans=0;
for(int i=0;i<n;i++) ans+=abs(p[i]-i);
int prer=0;
for(ii range:ranges)
{
int l=range.fi; int r=range.se;
//cerr<<"INTERVAL : "<<l<<' '<<r<<'\n';
if(l>=prer) mxans+=l-prer;
prer=max(r,prer);
}
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);
}
