#include <cstdio>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <tuple>
#include <climits>
using namespace std;
bool isSubtask3(int s) {return s==0;}
bool isSubtask4(int n) {return n<=1000;}
long long subtask3(vector<int> p, int s = 0, int e = -1 , int dir = 1) {
int n = p.size(), last = s;
if (e==-1) e = n-1;
long long total = 0;
for(int i=s; dir==1 && i<=e || dir==-1 && i>=e; i += dir) {
if (i==p[i]) continue;
if (dir*(i-last) > 0) total += abs(i-last)*2;
total += abs(p[i]-i);
last = dir==1? max(last,p[i]):min(last,p[i]);
}
return total;
}
long long cal(vector<int> p, int l, int r, int lmost, int rmost, vector<vector<long long>>& dp) {
if (dp[l][r]!=LLONG_MAX) return dp[l][r];
int n = p.size();
long long temp1=LLONG_MAX, temp2=LLONG_MAX;
if (l>0) {
temp1 = abs(p[l-1]-(l-1)); if(l-1 < lmost) temp1 += 2;
int lmostN = min(lmost,min(l-1,p[l-1])), rmostN = max(rmost,p[l-1]);
temp1 += cal(p,l-1,r,lmostN,rmostN,dp);
}
if (r<n-1) {
temp2 = abs(p[r+1]-(r+1)); if(r+1 > rmost) temp2 += 2;
int lmostN = min(lmost,p[r+1]), rmostN = max(rmost,max(r+1,p[r+1]));
temp2 += cal(p,l,r+1,lmostN,rmostN,dp);
}
dp[l][r] = min(temp1,temp2);
return dp[l][r];
}
long long subtask4(vector<int> p, int s) {
int n = p.size();
// long long move = 0;
int start; for(start = 0; start < s; start++) if(start!=p[start]) break;
int end; for(end = n-1; end > s; end--) if(end!=p[end]) break;
for(int i = 0; i <= end-start; i++) p[i] = p[i+start]-start;
s -= start; n = end-start+1; p.resize(n);
vector<vector<long long>> dp(n,vector<long long>(n,LLONG_MAX));
dp[0][n-1]=0;
int l=s, r=s, lmost = min(s,p[s]), rmost = max(s,p[s]);
return cal(p,l,r,lmost,rmost,dp)+abs(p[s]-s);
}
tuple<int,int,long long> extend(vector<int> p, int l, int r, int lmost, int rmost, int move) {
int n = p.size();
while(l> lmost || r < rmost) {
int idx;
if (l > max(lmost,0)) idx == --l;
else if (r < min(rmost,n-1)) idx == ++r;
move += abs(p[idx]-idx);
lmost = min(lmost,p[idx]);
rmost = max(rmost,p[idx]);
}
return make_tuple(l,r,move);
}
long long fulltask(vector<int> p, int s) {
int n = p.size();
int start; for(start = 0; start < s; start++) if(start!=p[start]) break;
int end; for(end = n-1; end > s; end--) if(end!=p[end]) break;
for(int i = 0; i <= end-start; i++) p[i] = p[i+start]-start;
s -= start; n = end-start+1; p.resize(n);
int l=s, r=s, lmost = min(s,p[s]), rmost = max(s,p[s]);
long long total=abs(p[s]-s), sumL=0, sumR=0, moveL=0, moveR=0;
while(0<l || r<n-1) {
// printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
// printf("l=%d, r=%d, lmost=%d, rmost=%d\n\n",l,r,lmost,rmost);
if(r < n-1 && (l <= 0 || moveR < moveL || moveR == moveL && r < rmost)) {
if(rmost <= r) moveR++;
r++;
sumR += abs(p[r]-r);
rmost = max(rmost,max(r,p[r]));
lmost = min(lmost,p[r]);
if (lmost <= l) {moveL = 0; total+=sumR+moveR*2; moveR=0; sumR=0;}
}
else if(0 < l && (r >= n-1 || moveR > moveL || moveR == moveL && r >= rmost)) {
if (l <= lmost) moveL++;
l--;
sumL += abs(p[l]-l);
lmost = min(lmost,min(l,p[l]));
rmost = max(rmost,p[l]);
if (r <= rmost) {moveR = 0; total+=sumL+moveL*2; moveL=0; sumL=0;}
l--;
}
}
// printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
// printf("l=%d, r=%d, lmost=%d, rmost=%d\n",l,r,lmost,rmost);
total += sumL + moveL*2;
total += sumR + moveR*2;
return total;
}
long long minimum_walk(std::vector<int> p, int s) {
// if (isSubtask3(s)) return subtask3(p);
// if (isSubtask4(s)) return subtask4(p,s);
return fulltask(p,s);
}
