#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 ;
const ll inf = 1e18+10 ;
using namespace std ;
//Tentando uma ideia (provavelmente vai dar errado mas vamos nessa)
vector<pii> intervalo ;
int n , L , R ;
int dist[MAX] ;
void bfs(int inicio)
{
int l = inicio , r = inicio ;
priority_queue<pii, vector<pii> , greater<pii> > fila ;
fila.push(make_pair(0,inicio)) ;
lp(i,0,n) dist[i] = n+5;
dist[inicio] = 0 ;
while(!fila.empty())
{
int x = fila.top().ss ;
int d = fila.top().ff ;
fila.pop() ;
if(d != dist[x]) continue ;
l = min(l, intervalo[x].ff );
r = max(r, intervalo[x].ss ) ;
vector<pii> adj ;
if(x > L )
{
if( x-1 >= l && x <= r )
adj.push_back(make_pair(x-1,0)) ;
else adj.push_back(make_pair(x-1, 1)) ;
}
if(x+1 <= R )
{
if( x >= l && x+1 <= r )
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 ));
}
}
}
long long minimum_walk(vector<int> p, int s)
{
n = sz(p) ;
ll ans = 0LL ;
lp(i,0,n) ans += (ll)(abs(p[i]-i)) ;
L = 0 ;
R = n-1 ;
while(L < s && p[L] == L ) L++ ;
while(R > s && p[R] == R) R-- ;
vector<bool> vis( n, false ) ;
intervalo.resize(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) ;
}
ll gordura = inf ;
vector<int> distBase(n) ;
bfs(s) ;
lp(i,0,n) distBase[i] = dist[i] ;
for(int i = L ; i <= R ; i++ )
{
bfs(i) ;
gordura = min(gordura, (ll)distBase[i] + dist[L] + dist[R]) ;
}
return ans + 2LL*gordura ;
}
