#include "books.h"
#include <vector>
#include <map>
#include <queue>
typedef struct range range;
struct range
{
int e;
long long m;
};
// bool operator<(range a, range b)
// {
// return a.s < b.s;
// }
int vis[1000005];
int still[1000005];
long long abs(long long a)
{
return (a < 0)?-a:a;
}
long long min(long long a, long long b)
{
return (a < b)?a:b;
}
long long max(long long a, long long b)
{
return (a > b)?a:b;
}
long long minimum_walk(std::vector<int> p, int ss) {
std::map<int, range> R;
std::queue<int> Q;
int i, n = p.size();
int s, e;
long long m;
for (i = 0; i < n; i++)
still[i] = 1;
for (i = 0; i < n; i++)
{
if (!vis[i])
{
s = i;
e = i;
m = 0;
while (!Q.empty())
Q.pop();
while (!vis[i])
{
vis[i] = 1;
Q.push(i);
m += abs(p[i] - i);
i = p[i];
s = min(s, i);
e = max(e, i);
}
// printf("%d %d %lld\n", s, e, m);
if (m != 0)
{
R.insert(std::make_pair(s, range{e, m}));
while (!Q.empty())
{
still[Q.front()] = 0;
Q.pop();
}
}
}
}
std::map<int, range>::iterator it, it2;
for (it = R.begin(); it != R.end();)
{
if (it != R.begin() && it->second.e < it2->second.e)
{
it2->second.m += it->second.m;
it = R.erase(it);
}
else if (it != R.begin() && it2->second.e > it->first)
{
it2->second.m += it->second.m;
it2->second.e = it->second.e;
it = R.erase(it);
}
else
{
it2 = it;
it++;
}
}
long long Ans = 0;
int stop = 0;
// for (i = 0; i < n; i++)
// printf("%d ", still[i]);
// printf("\n");
if (still[ss])
{
it = R.upper_bound(ss);
if (it != R.begin() && it != R.end())
{
it--;
if (it->second.e < ss)
stop = 1;
}
if (!stop)
{
for (i = ss; i >= 0 && still[i]; i--);
if (i >= 0) Ans = 2LL*(ss - i);
else Ans = 1e18;
// printf("i%d\n", i);
for (i = ss; i < n && still[i]; i++);
if (i < n) Ans = min(Ans, 2LL*(i - ss));
// printf("i%d\n", i);
}
}
if (Ans == 1e18)
Ans = 0;
for (it = R.begin(); it != R.end(); it++)
{
// printf("%d %d %lld\n", it->first, it->second.e, it->second.m);
Ans += it->second.m;
if (it != R.begin())
Ans += 2LL*(it->first - it2->second.e);
it2 = it;
}
return Ans;
}
