#include "books.h"
#include <bits/stdc++.h>
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
const int MAX = 1e6+10 ;
using namespace std ;
//Tentando uma ideia (provavelmente vai dar errado mas vamos nessa)
int bit[MAX] ;
void upd(int pos, int val)
{
if(pos == 0 ) return ;
for(int i = pos ; i < MAX ; i += (i&-i) )
bit[i] = max(bit[i] , val) ;
}
int qry(int pos)
{
if(pos == 0) return -1 ;
int tot = -1 ;
for(int i = pos ; i > 0 ; i -= (i&-i) )
tot = max(tot, bit[i]);
return tot ;
}
long long minimum_walk(vector<int> p, int s)
{
int n = sz(p) ;
ll ans = 0LL ;
lp(i,0,n) ans += (ll)(abs(p[i]-i)) ;
int L = 0 ;
int R = n-1 ;
while(L < s && p[L] == L ) L++ ;
while(R > s && p[R] == R) R-- ;
vector<bool> vis( n, false ) ;
vector<pii> intervalo(n, make_pair(-1,-1) ) ;
for(int i = L ; i <= R ; i++ )
{
if(vis[i]) continue ;
vector<int> List ;
int x = i , l = i , r = i;
while(!vis[x])
{
vis[x] = true ;
List.push_back(x) ;
l = min(l,x) ;
r = max(r,x) ;
x = p[x] ;
}
for(auto e : List ) intervalo[e] = make_pair(l,r) ;
}
vector<int> dist(n, n+5 ) ;
priority_queue< pii , vector<pii> , greater<pii> > fila ;
fila.push(make_pair(0,s)) ;
dist[s] = 0 ;
upd( intervalo[s].ff+1 , intervalo[s].ss ) ;
while(!fila.empty())
{
int x = fila.top().ss ;
int d = fila.top().ff ;
fila.pop() ;
if(dist[x] != d) continue ;
vector<pii> adj ;
if(x)
{
if( qry(x) >= x )
adj.push_back(make_pair(x-1,0)) ;
else adj.push_back(make_pair(x-1, 1)) ;
}
if(x+1 < n)
{
if( qry(x+1) >= x+1)
adj.push_back(make_pair(x+1, 0));
else adj.push_back(make_pair(x+1, 1 ) ) ;
}
for(auto e : adj)
{
int y = e.ff ;
int cost = e.ss ;
if(dist[y]<= cost+dist[x]) continue ;
dist[y] = dist[x]+cost ;
fila.push(make_pair(dist[y] , y ));
upd( intervalo[y].ff+1, intervalo[y].ss ) ;
}
}
ll toSum = dist[L] + dist[R] ;
ll mx = 0 ;
for(int i = L ; i <= R ; i++ )
if(intervalo[i].ff <= s && intervalo[i].ss >= s )
mx = max(mx, (ll)dist[i]) ;
toSum -= mx ;
return ans + 2LL*toSum ;
}
