// moreflags=grader.cpp
// 11
#include "books.h"
#include<algorithm>
#include<numeric>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<climits>
long long minimum_walk(std::vector<int> p, int s) {
// assert(std::is_permutation(begin(p), end(p)));
assert(s>=0); assert(s<(int)p.size());
//if(p.size()>1000) return -1;
int64_t result{};
for(int index=0; index<(int)p.size(); ++index){
if(index<p[index]){
result+=p[index]-index;
}
}
struct Dsu{
std::vector<int> data;
void reset(int number){data.assign(number, -1);}
int root(int node){return data[node]>=0 ? data[node]=root(data[node]): node;}
bool join(int first, int sec){
first=root(first); sec=root(sec);
if(first==sec) return false;
data[first]=sec;
return true;
}
};
Dsu dsu; dsu.reset((int)p.size());
for(int first=0; first<(int)p.size(); ++first) if(p[first]!=first)
for(int sec=0; sec<first; ++sec) if(p[sec]!=sec){
auto const [p1, p2]=std::minmax({
std::minmax({first, p[first]}),
std::minmax({sec, p[sec]})
});
auto const [a, b]=p1; auto const [c, d]=p2;
if(c<=b and b<=d){// partially intersect
dsu.join(first, sec);
}
}
std::vector<std::vector<int>> components(p.size());
for(int index=0; index<(int)p.size(); ++index)
if(p[index]!=index)
components[dsu.root(index)].push_back(index);
components.erase(std::remove_if(begin(components), end(components), [&](auto const& it){
return it.empty();}), components.end());
std::vector<int> left(p.size(), INT_MAX), right(p.size(), -1);
for(auto const& it: components)
for(auto item: it)
left[item]=it[0], right[item]=it.back();
int left_=std::min(s, left[s]), right_=std::max(s, right[s]);
while(true){
int left1=left_, cost1=0;
while(left1>=0 and right[left1]<=right_){
if(left[left1]<=left1)
left1=left[left1];
assert(left[left1]>=left1);
++cost1;
--left1;
}
int right2=right_, cost2=0;
while(right2<(int)p.size() and left[right2]>=left_){
if(right[right2]>=right2)
right2=right[right2];
assert(right[right2]<=right2);
++cost2;
++right2;
}
assert((left1>=0)==(right2<(int)p.size()));
if(left1<0){
break;
}
if(cost1<cost2){
result+=cost1;
}else{
result+=cost2;
}
assert(left[left1]==left[right2]);
assert(right[left1]==right[right2]);
left_=left[left1]; right_=right[right2];
assert(left[left_]>=left_);
assert(right[right_]<=right_);
}
while(true){
assert(left[left_]>=left_);
int left1=left_;
while(left1>=0 and left[left1]>=left1) --left1;
if(left1<0) break;
assert(right[left1]<left_);
result+=left_-left1; left_=left[left1];
}
while(true){
assert(right[right_]<=right_);
int right2=right_;
while(right2<(int)p.size() and right[right2]<=right2) ++right2;
if(right2==(int)p.size()) break;
assert(left[right2]>right_);
result+=right2-right_; right_=right[right2];
}
return result*2;
}
