#include <bits/stdc++.h>
using namespace std;
#include "books.h"
struct SegTree{
vector<long long> segtree;
SegTree(int n){
segtree.resize((1LL<<((long long)(ceil(log2(n)+1))))-1,0ll);
}
void update(int node){
node+=segtree.size()/2;
segtree[node]++;
while (node){
node=(node-1)/2;
segtree[node]++;
}
}
long long query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
if (r==-1) r = segtree.size()/2;
if (l>=tarl && r<=tarr) return segtree[node];
if (l>tarr || r<tarl) return 0ll;
int mid = l+(r-l)/2;
long long lnode = query(tarl, tarr, l, mid, node*2+1);
long long rnode = query(tarl, tarr, mid+1, r, node*2+2);
return lnode+rnode;
}
};
long long minimum_walk(std::vector<int> p, int s) {
//number of inversions*2+max pos such that p_i!=i-last non inversion
//a*2+b-c
long long a=0, b=-1, c=0;
int n = p.size();
SegTree segtree(n);
for (int i = n-1; i >= 0; i--){
if (p[i]!=i){
b=i;
break;
}
}
if (b==-1) return 0;
for (int i = 0; i < b; i++){
if (p[i]<p[b]) c++;
}
for (int i = 0; i < n; i++){
a+=segtree.query(p[i],n-1);
segtree.update(p[i]);
}
return a*2+b-c;
}
