/*
PROG: template
LANG: C++11
_____
.' '.
/ 0 0 \
| ^ |
| \ / |
\ '---' /
'._____.'
*/
#include <bits/stdc++.h>
#include "books.h"
using namespace std;
template<class T>
void readi(T &x)
{
T input = 0;
bool negative = false;
char c = ' ';
while (c < '-')
{
c = getchar();
}
if (c == '-')
{
negative = true;
c = getchar();
}
while (c >= '0')
{
input = input * 10 + (c - '0');
c = getchar();
}
if (negative)
{
input = -input;
}
x = input;
}
template<class T>
void printi(T output)
{
if (output == 0)
{
putchar('0');
return;
}
if (output < 0)
{
putchar('-');
output = -output;
}
int aout[20];
int ilen = 0;
while(output)
{
aout[ilen] = ((output % 10));
output /= 10;
ilen++;
}
for (int i = ilen - 1; i >= 0; i--)
{
putchar(aout[i] + '0');
}
return;
}
template<class T>
void ckmin(T &a, T b)
{
a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
a = max(a, b);
}
long long randomize(long long mod)
{
return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;
#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 1013
long long normalize(long long x, long long mod = INF)
{
return (((x % mod) + mod) % mod);
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int N, S, K;
vector<int> arr;
bool vis[MAXN];
bool useless[MAXN];
vector<int> cyc[MAXN];
int id[MAXN];
int lt[MAXN], rt[MAXN];
ll ans = 0;
bool seen[MAXN][MAXN];
bool ex[MAXN][MAXN];
pii ext[MAXN][MAXN];
int dp[MAXN][MAXN];
int mintable[25][MAXN], maxtable[25][MAXN];
int lg2[MAXN];
vector<int> pts;
int query(int L, int R, bool flag)
{
//query min
//floor of log2?
int SZ = R - L + 1, lg = lg2[SZ];
if (flag)
{
return max(maxtable[lg][L], maxtable[lg][R - (1 << lg) + 1]);
}
return min(mintable[lg][L], mintable[lg][R - (1 << lg) + 1]);
}
pii extend(int L, int R)
{
if (ex[L][R])
{
return ext[L][R];
}
ex[L][R] = true;
int lo = L, hi = R;
while(true)
{
int lt = query(lo, hi, 0), rt = query(lo, hi, 1);
if (lt == lo && rt == hi)
{
break;
}
ckmin(lo, lt); ckmax(hi, rt);
}
ext[L][R] = MP(lo, hi);
return ext[L][R];
}
int solve(int L, int R)
{
if (seen[L][R])
{
return dp[L][R];
}
seen[L][R] = true;
pii trans;
if (L == 0)
{
if (R == N - 1)
{
dp[L][R] = 0;
}
else
{
trans = extend(L, R + 1);
dp[L][R] = 2 + solve(trans.fi, trans.se);
}
}
else
{
if (R == N - 1)
{
trans = extend(L - 1, R);
dp[L][R] = 2 + solve(trans.fi, trans.se);
}
else
{
trans = extend(L - 1, R);
dp[L][R] = 2 + solve(trans.fi, trans.se);
// if (L == 420 && R == 428) cerr << trans.fi << ' ' << trans.se << ' ' << dp[L][R] << endl;
trans = extend(L, R + 1);
ckmin(dp[L][R], 2 + solve(trans.fi, trans.se));
// if (L == 420 && R == 428) cerr << trans.fi << ' ' << trans.se << ' ' << dp[L][R] << endl;
}
}
// cerr << L << ' ' << R << ' ' << dp[L][R] << endl;
return dp[L][R];
}
ll minimum_walk(vector<int> p, int s)
{
s = p[s];
for (int j = p.size() - 1; j > s; j--)
{
if (p[j] == j)
{
useless[j] = true;
}
else
{
break;
}
}
for (int j = 0; j < s; j++)
{
if (p[j] == j)
{
useless[j] = true;
}
else
{
break;
}
}
for (int j = 0; j < p.size(); j++)
{
if (!useless[j])
{
arr.PB(p[j]);
}
}
if (arr.empty()) return 0;
N = arr.size();
int sm = INF;
for (int i = 0; i < N; i++)
{
ckmin(sm, arr[i]);
if (arr[i] == s)
{
S = i;
}
}
// cerr << S << ' ' << arr[S] << endl;
for (int i = 0; i < N; i++)
{
arr[i] -= sm;
// cerr << arr[i] << ' ';
}
// cerr << endl;
for (int i = 0; i < N; i++)
{
if (vis[i])
{
continue;
}
int u = i;
do
{
vis[u] = true;
cyc[K].PB(u);
u = arr[u];
}
while(u != i);
K++;
}
for (int i = 0; i < K; i++)
{
for (int u : cyc[i])
{
id[u] = i;
}
}
for (int i = 0; i < K; i++)
{
for (int j = 1; j < cyc[i].size(); j++)
{
ans += abs(cyc[i][j] - cyc[i][j - 1]);
}
ans += abs(cyc[i].back() - cyc[i][0]);
lt[i] = INF, rt[i] = -INF;
for (int u : cyc[i])
{
ckmin(lt[i], u);
ckmax(rt[i], u);
}
}
for (int i = 0; i < N; i++)
{
mintable[0][i] = lt[id[i]];
maxtable[0][i] = rt[id[i]];
vis[i] = false;
// cerr << lt[i] << ' ' << rt[i] << endl;
}
for (int i = 0; i <= 20; i++)
{
for (int j = (1 << i); j < (2 << i) && j <= N; j++)
{
lg2[j] = i;
}
}
for (int i = 1; i <= 20; i++)
{
for (int j = 0; j < N; j++)
{
if (j + (1 << i) - 1 >= N) continue;
mintable[i][j] = min(mintable[i - 1][j], mintable[i - 1][j + (1 << (i - 1))]);
maxtable[i][j] = max(maxtable[i - 1][j], maxtable[i - 1][j + (1 << (i - 1))]);
}
}
// cerr << extend(419, 428).fi << ' ' << extend(419, 428).se << endl;
pii start = extend(S, S);
solve(start.fi, start.se);
ans += dp[start.fi][start.se];
//u -> arr[u]
//x -> p[x] -> p[p[x]] etc
//you can swap, at the cost of the difference in pos
return ans;
}
