#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 1e6 + 5;
int n;
long long minimum_walk(std::vector<int> p, int s) {
n = sz(p);
vector<int> col(n, 0);
vector<int> reqs(n + 2, 0);
int flag = 0;
multiset<int> lhf;
ll sum = 0;
for(int i = 0; i < n; i++) {
if(col[i] == 0) {
flag++;
int x = i, cnt = 0;
set<int> vals;
while(col[x] != flag) {
col[x] = flag;
sum += abs(x - p[x]);
x = p[x];
cnt++;
vals.emplace(x);
}
int L = *vals.begin();
int R = *vals.rbegin();
reqs[L]++;
reqs[R]--;
}
}
for(int i = 1; i <= n; i++)
reqs[i] += reqs[i - 1];
int l = 0, r = n - 1;
while(l < s && p[l] == l) l++;
while(r > s && p[r] == r) r--;
r--;
if(s != 0)
assert(r == n - 2);
ll mn = 0;
for(int i = l; i <= r; i++) mn += reqs[i] == 0;
return sum + mn * 2;
}
/**
Anul asta se da centroid.
-- Surse oficiale
*/
