#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6;
const ll inf = 1e18;
class fenwick{
private:
vector <ll> fen;
ll n;
public:
void init(ll sz,ll x = 0){
fen.resize(sz);
n = sz;
for(ll i = 0;i < n;i++)fen[i] = x;
};
void add(ll pos,ll nr = 1){
for(ll i = pos;i < n;i|=(i + 1)){
fen[i] = max(fen[i],nr);
}
};
ll get(ll pos,ll rinit = 0){
ll r = rinit;
for(ll i = pos;i >= 0;i&=(i + 1),i--){
r+=fen[i];
}
return r;
}
};
fenwick fen;
bool vis[N];
vector <ll> points;
long long minimum_walk(std::vector<int> p, int s) {
ll n = p.size();
fen.init(n);
ll ans = 0;
for(ll i= 0;i < n;i++){
ans+=abs(i - p[i]);
if(!vis[i]){
ll nr = p[i];
while(nr != i){
points.push_back(nr);
nr = p[nr];
}
points.push_back(nr);
if(points.size() == 1){
points.clear();
continue;
}
ll a = -1,b = inf;
for(auto j:points){
vis[j] = 1;
if(j <= s)a = max(a,j);
if(j >= s)b = min(b,j);
}
fen.add(a + 1,b);
points.clear();
}
}
ll mn = inf;
for(ll i = 0;i <= s;i++){
mn = min(mn,fen.get(i) - i);
}
//cout<<ans<<' '<<mn<<'\n';
ans+=2*mn;
return ans;
}
