#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
long long minimum_walk(vi p, int s) {
int N=p.size();
long long total_distance=0;
vi cmin; //cycle min and max positions
vi cmax;
vector<bool> cfound;
int C=0;//number of cycles
vector<bool> visited(N,false);
vi cycleof(N,0);
for(int i=0; i<N; i++) {
if(!visited[i]) {
//cout << "new cycle from " << i << endl;
visited[i]=true;
if(p[i]!=i) {
cmin.push_back(i); //create new cycle
cmax.push_back(i);
cfound.push_back(false);
total_distance+=abs(i-p[i]);
cycleof[i]=C;
for(int current=p[i]; current!=i; current=p[current]) { //add other points
cmin[C]=min(cmin[C],current);
cmax[C]=max(cmax[C],current);
total_distance+=abs(current-p[current]);
visited[current]=true;
cycleof[current]=C;
}
C++;
} else {
cycleof[i]=-1;
}
}
}
//cout << total_distance <<" for walking with books, cycles: " << C << endl;
int foundc=0;
int ml,mr,l,r; //maxl maxr currentl currentr
ml=mr=l=r=s;
while(foundc<C) { //not all cycles have been found
//cout << ml << ' ' << l << ' ' << r << ' ' << mr << ' ' << foundc << endl;
if(ml>l and mr<r) { //all directly reachable cycles visited
for(int d=1; d<N; d++) {
if(mr+d<N and cycleof[mr+d]!=-1 and !cfound[cycleof[mr+d]]) { //found one to the right
r=mr=mr+d;
total_distance+=2*d;
//cout << "walking an extra " << d << " meters (twice) to reach other cycle to the left\n";
break;
} else if(ml-d>=0 and cycleof[ml-d]!=-1 and !cfound[cycleof[ml-d]]) { //found one to the left
l=ml=ml-d;
total_distance+=2*d;
//cout << "walking an extra " << d << " meters (twice) to reach other cycle to the right\n";
break;
}
}
}
while(ml<=l) { //search for new cycles in reachable range
int i=l;
if(cycleof[i]!=-1 and !cfound[cycleof[i]]) {
cfound[cycleof[i]]=true;
ml=min(ml,cmin[cycleof[i]]);
mr=max(mr,cmax[cycleof[i]]);
foundc++;
//cout << "found cycle " << cycleof[i] << " at " << i << endl;
}
l--;
}
while(mr>=r) {
int i=r;
if(cycleof[i]!=-1 and !cfound[cycleof[i]]) {
cfound[cycleof[i]]=true;
ml=min(ml,cmin[cycleof[i]]);
mr=max(mr,cmax[cycleof[i]]);
foundc++;
//cout << "found cycle " << cycleof[i] << " at " << i << endl;
}
r++;
}
//clock_t start_time = clock();
// looping till required time is not achieved
//while (clock() < start_time + 1000000);
}
return total_distance;
}
