#include <bits/stdc++.h>
#include "books.h"
#define rep(i,n) for(int i = 0; i < n; i++)
#define lint long long
using namespace std;
vector<int>fen;
int n;
void up(int i, int val){
i++;
for(; i <=n; i+=i&-i){
fen[i]+=val;
}
}
int get(int i){
i++;
int s=0;
for(;i>0;i-=i&-i){
s+=fen[i];
}
return s;
}
int get_range(int l, int r){
return get(r) - get(l-1);
}
long long minimum_walk(std::vector<int> p, int s) {
n = p.size();
fen.resize(n+1);
vector<bool>unhappy(n);
rep(i,n)
if(p[i]!=i) {up(i,1); unhappy[i]=true;}
lint cost=0;
bool first=true;
while(get(n-1)>0){
int begin=-1, e=n;
while(e-begin>1){
int cur = (begin+e)/2;
if(get_range(max(0, s-cur), min(n-1, s+cur)))
{
e=cur;
} else
{
begin=cur;
}
}
if(unhappy[max(0, s-e)])
{
s=max(0, s-e);
} else if (unhappy[min(n-1, s+e)])
{
s=min(n-1, s+e);
}
if(first){
first=false;
up(s, -1);
}
cost+=e;
unhappy[s]=false;
cost+=abs(p[s]-s);
s=p[s];
up(s, -1);
}
return cost+s;
}
