#include "books.h"
#include <cstdlib>
#include <queue>
#include <utility>
const int MAXN = 1e6;
int belongsTo[MAXN];
std::pair<int, int> cycInter[MAXN];
std::queue<std::pair<int, int>> toCheck;
bool gonnaCheck[MAXN];
void processcycle(int cycle, int &left, int &right)
{
gonnaCheck[cycle] = true;
if (cycInter[cycle].first < left)
{
toCheck.emplace(cycInter[cycle].first, left);
left = cycInter[cycle].first;
}
if (cycInter[cycle].second > right)
{
toCheck.emplace(right, cycInter[cycle].second);
right = cycInter[cycle].second;
}
}
long long minimum_walk(std::vector<int> p, int s)
{
int tables = p.size();
std::fill_n(belongsTo, tables, -1);
long long minWalk = 0;
int cycles = 0;
for (int iTable = 0; iTable < tables; iTable++)
if (belongsTo[iTable] == -1)
{
int leftMost = tables, rightMost = 0;
int curTable = iTable;
while (belongsTo[curTable] == -1)
{
leftMost = std::min(leftMost, curTable);
rightMost = std::max(rightMost, curTable);
belongsTo[curTable] = cycles;
minWalk += (long long)std::abs(curTable - p[curTable]);
curTable = p[curTable];
}
cycInter[cycles] = { leftMost, rightMost + 1 };
cycles++;
}
int left = s, right = s;
processcycle(belongsTo[s], left, right);
do {
while (!toCheck.empty())
{
std::pair<int, int> checkingInter = toCheck.front();
toCheck.pop();
for (int iTable = checkingInter.first; iTable < checkingInter.second; iTable++)
if (!gonnaCheck[belongsTo[iTable]])
processcycle(belongsTo[iTable], left, right);
}
minWalk += 2;
if (left != 0)
processcycle(belongsTo[left - 1], left, right);
else if (right != tables)
processcycle(belongsTo[right], left, right);
else
minWalk -= 2;
} while (left != 0 && right != tables);
return minWalk;
}
