// moreflags=grader.cpp
// 11
// a little faster.
#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(s>=0); assert(s<(int)p.size());
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());
std::vector<int> depth(p.size(), -1); // in stack (-2: already popped)
struct Item{
int firstConnect; // stack[firstConnect]..=current item should be connected (or INT_MAX)
int id;
};
std::vector<Item> stack;
for(int pos=0; pos<(int)p.size(); ++pos) if(pos!=p[pos]){
dsu.join(pos, p[pos]);
for(auto id: {pos, p[pos]}){
if(depth[id]<0){
assert(depth[id]==-1);
depth[id]=(int)stack.size();
stack.push_back({INT_MAX, id});
}else{
auto const curDepth=depth[id];
assert(stack[curDepth].id==id);
if(stack[curDepth].firstConnect<curDepth){
stack[curDepth-1].firstConnect=std::min(stack[curDepth-1].firstConnect,
stack[curDepth].firstConnect);
if(stack[curDepth-1].id>=0)
dsu.join(stack[curDepth-1].id, id);
}
stack[curDepth].id=-1;
bool const removeBack=curDepth==(int)stack.size()-1;
depth[id]=-2;
if(not removeBack){
dsu.join(id, stack.back().id);
}
int minFirstConnect=curDepth;
while(not stack.empty() and stack.back().id<0){
assert(removeBack);
assert(stack.back().id==-1);
minFirstConnect=std::min(minFirstConnect, stack.back().firstConnect);
stack.pop_back();
}
if(minFirstConnect<(int)stack.size()){
stack.back().firstConnect=std::min(stack.back().firstConnect,
minFirstConnect);
dsu.join(id, stack.back().id);
}
}
}
}
std::vector<std::array<int, 2>> rootBound(p.size(), {{INT_MAX, INT_MIN}});
for(int index=0; index<(int)p.size(); ++index){
auto const t=dsu.root(index);
rootBound[t]={{
std::min(rootBound[t][0], index),
std::max(rootBound[t][1], index)
}};
}
std::vector<int> left(p.size(), INT_MAX), right(p.size(), -1);
for(int index=0; index<(int)p.size(); ++index) if(p[index]!=index){
auto const t=dsu.root(index);
left[index]=rootBound[t][0];
right[index]=rootBound[t][1];
}
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;
}
