#include "books.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
#define F first
#define S second
int a[N] , n , dp[N][N] , match[N];
bool marked[N] , ch[N];
vector <int> adj[N];
bool try_kuhn(int v)
{
marked[v] = true;
for(auto u : adj[v])
{
if(match[u] == -1)
{
match[u] = v;
match[v] = u;
return true;
}
if(!marked[match[u]] && try_kuhn(match[u]))
{
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
int Matching(int s)
{
for(int i = 0 ; i < n ; i++)
match[i] = -1;
bool flg = true;
int res = 0;
while(flg)
{
flg = false;
for(int i = 0 ; i < n ; i++)
marked[i] = false;
for(int i = 0 ; i <= s ; i++) if(match[i] == -1 && try_kuhn(i))
{
res++;
flg = true;
}
}
return res;
}
long long minimum_walk(vector<int> p, int s) {
n = p.size();
long long ans = 0;
int cnt = (p[0] == 0 ? 0 : 1);
marked[p[0]] = true;
for(int i = 1 ; i < n ; i++)
{
a[i] = cnt;
ans += 2 * cnt;
//cout << i << " : " << cnt << endl;
if(p[i] > i)
{
cnt++;
marked[p[i]] = true;
}
if(marked[i])
cnt--;
}
int L = 0 , R = n - 1;
for(int i = n - 1 ; i > s ; i--)
{
if(p[i] != i)
break;
R--;
}
for(int i = 0 ; i < s ; i++)
{
if(p[i] != i)
break;
L++;
}
vector <pair<int , int>> all;
for(int l = L ; l <= s ; l++) for(int r = s ; r <= R ; r++)
{
bool flg = true;
for(int i = l ; i <= r ; i++) if(p[i] < l || p[i] > r)
{
flg = false;
break;
}
if(!flg)
continue;
if(l == L && r == R)
continue;
if(l == L)
ch[r + 1] = true;
else if(r == R)
ch[l] = true;
else
all.push_back({l , r + 1});
}
vector <pair<int , int>> vec;
for(auto u : all) if(!ch[u.F] && !ch[u.S])
{
adj[u.F].push_back(u.S);
adj[u.S].push_back(u.F);
}
for(int i = 0 ; i < n ; i++) if(ch[i])
ans += 2;
ans += 2 * Matching(s);
return ans;
}
