#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class NarrowPassage { public:
int minDist(int L, vector <int> a, vector <int> b)
{
sortab(a,b);
int r = 0x3fffffff;
r = min(r, solve_with_partial(L, a, b, 0, "LR", 0));
r = min(r, solve_with_partial(L, a, b, 0, "RL", 0));
return r;
}
void sortab(vector <int>& a, vector <int>& b)
{
const int N = a.size();
vector<pair<int,int>> ab;
for(int i=0; i<N; ++i)
ab.emplace_back(a[i], b[i]);
sort(ab.begin(), ab.end());
for(int i=0; i<N; ++i) {
a[i] = ab[i].first;
b[i] = ab[i].second;
}
}
int solve_with_partial(int L, vector<int> a, vector<int> b, int m, const string& pat, int pati)
{
const int N = a.size();
int r = 0;
if(m) {
if(pat[pati] == 'L') {
vector<int> idx;
for(int i=0; i<m; ++i)
idx.push_back(i);
sort(idx.begin(), idx.end(), [&](int i, int k){
return b[i]<b[k];
});
for(int ii=0; ii<idx.size(); ++ii) {
int i = idx[ii];
int np = ii+1;
r += a[i] + np;
a[i] = np;
}
} else {
vector<int> idx;
for(int i=m; i<N; ++i)
idx.push_back(i);
sort(idx.begin(), idx.end(), [&](int i, int k){
return b[i]<b[k];
});
for(int ii=0; ii<idx.size(); ++ii) {
int i = idx[ii];
int np = L-(idx.size()-ii);
r += abs(L-a[i]) + abs(L-np);
a[i] = np;
}
}
sortab(a, b);
}
if(pati == pat.size())
return r + solve(L, a, b);
int best = 0x3fffffff;
for(int mm=0; mm<N; ++mm)
best = min(best, r + solve_with_partial(L, a, b, mm, pat, pati+1));
return best;
}
int solve(int L, const vector<int>& a, const vector<int>& b)
{
const int N = a.size();
vector<pair<int,int>> bad;
set<int> bar;
for(int i=0; i<N; ++i)
for(int k=i+1; k<N; ++k)
if(!(b[i]<b[k])) {
bad.emplace_back(i, k+1);
bar.insert(i);
bar.insert(k+1);
}
{
set<int> bar2 = bar;
for(int bb : bar)
for(auto& bi : bad) {
if(bi.first<bb && bb<bi.second)
{bar2.erase(bb); break;}
}
bar.swap(bar2);
}
if(bar.empty())
return noxchange(a, b, 0, N);
int r = 0x3fffffff;
for(int mid: bar) {
int ll = 0, rr = N;
for(auto& bi: bad) {
if(bi.second <= mid)
ll = max(ll, bi.second);
if(mid <= bi.first)
rr = min(rr, bi.first);
}
r = min(r, totheend(0, a, b, 0, ll) + noxchange(a, b, ll, rr) + totheend(L, a, b, rr, N));
}
return r;
}
int noxchange(const vector<int>& a, const vector<int>& b, int S, int E)
{
int result = 0;
for(int i=S; i<E; ++i)
result += abs(a[i] - b[i]);
return result;
}
int totheend(int END, const vector<int>& a, const vector<int>& b, int S, int E)
{
int result = 0;
for(int i=S; i<E; ++i)
result += abs(a[i] - END) + abs(END - b[i]);
return result;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, NarrowPassage().minDist(L, a, b));}
int main(){
CASE(0)
int L = 5;
int a_[] = {1, 2};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {3, 4};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
int _ = 4;
END
CASE(1)
int L = 10;
int a_[] = {3, 9};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {8, 6};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
int _ = 14;
END
CASE(2)
int L = 265467;
int a_[] = {133548, 103861, 29821, 199848, 92684, 219824, 215859, 62821, 172409, 109235,
38563, 148854, 24742, 174068, 205005, 75922, 87316, 5542, 57484, 40792,
25229, 152216, 21547, 22203, 84712, 231522, 235703, 184895, 100787, 174440,
156904, 84898, 185568, 108732, 260098, 89488, 221604, 104555, 165775, 90444,
81952, 149671, 209674, 22185, 45420, 41928, 16098, 65324, 90870, 35243};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {150289, 135139, 69841, 227226, 177427, 230314, 199175, 81572, 220468, 151049,
40009, 145963, 115246, 252932, 263651, 38434, 120096, 69576, 29789, 115046,
33310, 260771, 5723, 80733, 107864, 142447, 235490, 242149, 124564, 134602,
245962, 7078, 215816, 219864, 190499, 210237, 212894, 142760, 126472, 201935,
119308, 120211, 235235, 19446, 87314, 17286, 61990, 102050, 261812, 257};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
int _ = 7148670;
END
CASE(3)
int L = 1000000;
int a_[] = {706292, 756214, 490048, 228791, 567805, 353900, 640393, 562496, 217533, 934149,
938644, 127480, 777134, 999144, 41485, 544051, 417987, 767415, 971662, 959022,
670563, 34065, 518183, 750574, 546576, 207758, 159932, 429345, 670513, 271901,
476062, 392721, 774733, 502586, 915436, 120280, 951729, 699859, 581770, 268966,
79392, 888601, 378829, 350198, 939459, 644983, 605862, 721305, 269232, 137587};
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = {322468, 673534, 83223, 551733, 341310, 485064, 885415, 927526, 159402, 28144,
441619, 305530, 883149, 413745, 932694, 214862, 677401, 104356, 836580, 300580,
409942, 748444, 744205, 119051, 999286, 462508, 984346, 887773, 856655, 245559,
418763, 840266, 999775, 962927, 779570, 488394, 760591, 326325, 206948, 13999,
285467, 401562, 786209, 169847, 171326, 2901, 296531, 572035, 364920, 939046};
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
int _ = 45670501;
END
/*
CASE(4)
int L = ;
int a_[] = ;
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = ;
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
int _ = ;
END
CASE(5)
int L = ;
int a_[] = ;
vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
int b_[] = ;
vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
int _ = ;
END
*/
}
// END CUT HERE