#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)];
}
ll solve(vi p, int s)
{
//solve for s=0
int n=p.size();
int mn=n-1; int mx=0;
for(int i=0;i<p.size();i++)
{
if(p[i]!=i){mn=min(mn,i);mx=max(mx,i);}
}
int mxans=0; ll ans=0;
for(int i=0;i<n;i++) ans+=abs(p[i]-i);
queue<int> q; q.push(s);
int curl=s; int curr=s;
while(1)
{
while(!q.empty())
{
int u=q.front(); q.pop();
while(curl>p[u])
{
curl--; q.push(curl);
}
while(curr<p[u])
{
curr++; q.push(curr);
}
}
//after all the free operations
int distl=0; int distr=0;
bool touchr=0; bool touchl=0; //note that if it's useful they'll be touching the same pair
queue<int> ql,qr;
int curl2=curl; int curr2=curr;
while(1)
{
if(curl2<=mn) break;
curl2--; distl++; ql.push(curl2);
while(!ql.empty())
{
int u=ql.front(); ql.pop();
while(curl2>p[u])
{
curl2--; ql.push(curl2);
}
if(p[u]>=s) touchr=1;
}
if(touchr) break;
}
while(1)
{
if(curr2>=mx) break;
curr2++; distr++; qr.push(curr2);
while(!qr.empty())
{
int u=qr.front(); qr.pop();
while(curr2<p[u])
{
curr2++; qr.push(curr2);
}
if(p[u]<=s) touchl=1;
}
if(touchl) break;
}
if(touchl&&touchr)
{
mxans+=min(distl,distr);
while(curl>curl2)
{
curl--; q.push(curl);
}
while(curr<curr2)
{
curr++; q.push(curr);
}
}
else
{
mxans+=distl+distr; break;
}
}
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
{
int sum=0;
for(int i=0;i<p.size();i++) sum+=abs(i-p[i]);
int ans=get_naive(p,s);
int res=solve(p,s);
if(ans!=res)
{
cerr<<"WARRRRRRRRRRNING\n";
for(int v:p)
{
cerr<<v<<' ';
}
cerr<<'\n';
cerr<<ans<<' '<<res<<' '<<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);
}
