#include <bits/stdc++.h>
using namespace std;
/*
Giải thích tóm tắt các bước trong code:
- Ta có hoán vị ban đầu A[1..N], LƯU vị trí pos[v] = index của giá trị v trong A.
(Giả định A là hoán vị của {1..N}.)
- DP[k] sẽ là chi phí (số nghịch thế) tối thiểu để xây một hoán vị B sao cho
prefix B[1..k] (vốn gồm đúng tập {1..k} nhưng xếp thành một số khối đảo ngược liên tiếp)
đã “ổn định” và thỏa a_i < a_{i+1} + 2 trong prefix.
- Khi chuyển DP[j] → DP[k] (với j < k), ta thêm block mới {j+1, j+2, …, k}. Khối này
sẽ nằm ngay sau prefix j và được đặt theo thứ tự [k, k-1, …, j+1]. Việc “đặt” block này
phát sinh thêm một số nghịch thế (inversion) so với hoán vị ban đầu A:
1. Mọi giá trị > k trong phần đã xét (prefix cũ) sẽ “va” với mỗi h ∈ {j+1..k}.
2. Mọi giá trị g trong prefix cũ sao cho j < g < h, mỗi khi ta đặt h xuống sẽ “va” 1 lần.
Ở đây, chúng ta sẽ tiền tính hai mảng:
1) small_cnt[x][h] = số lượng các i < pos[h] sao cho A[i] nằm trong (x, h),
tức x < A[i] < h. (đóng góp kiểu “giữa j và h”)
2) big_cnt[k][h] = số lượng các i < pos[h] sao cho A[i] > k. (đóng góp kiểu “> k”)
- Với mỗi cặp (j,k), ta cần compute SUM_{h = j+1..k} [ big_cnt[k][h] + small_cnt[j][h] ].
Gọi sum_big[k][t] = ∑_{h=1..t} big_cnt[k][h],
sum_small[j][t] = ∑_{h=1..t} small_cnt[j][h].
Khi đó, chi phí thêm của block {j+1..k} là
cost_add(j→k) = ( sum_big[k][k] - sum_big[k][j] )
+ ( sum_small[j][k] - sum_small[j][j] ).
- Cuối cùng, DP[k] = min_{0 ≤ j < k} { DP[j] + cost_add(j→k) }.
Với DP[0] = 0 (tưởng tượng prefix rỗng, chưa xếp giá trị nào).
Độ phức tạp:
- Tính small_cnt[x][h] với ba vòng: x=0..N-1, h=x+1..N, rồi duyệt i=1..pos[h]-1 ⇒ O(N^3)
- Tính big_cnt[k][h] với ba vòng: k=1..N, h=1..k, rồi duyệt i=1..pos[h]-1 ⇒ O(N^3)
- Tạo prefix-sum sum_small và sum_big: O(N^2)
- DP: hai vòng k=1..N, j=0..k-1 ⇒ mỗi bước O(1) tra công thức, tổng O(N^2)
⇒ Tổng ≈ O(N^3), với N ≤ 200 là hoàn toàn khả thi.
*/
static const int MAXN = 200;
int N;
int A[MAXN+1]; // A[1..N]: hoán vị ban đầu (mỗi số từ 1..N đúng một lần)
int pos[MAXN+1]; // pos[v] = index i sao cho A[i] = v
// small_cnt[x][h] = số i < pos[h] sao cho x < A[i] < h
// defined for 0 <= x < h <= N
int small_cnt[MAXN+1][MAXN+1];
// big_cnt[k][h] = số i < pos[h] sao cho A[i] > k
// defined cho 1 <= k <= N, 1 <= h <= k (chỉ cần h <= k vì nếu h>k, block {j+1..k} không có h đó)
int big_cnt[MAXN+1][MAXN+1];
// sum_small[x][t] = ∑_{h=1..t} small_cnt[x][h]
// sum_big[k][t] = ∑_{h=1..t} big_cnt[k][h]
long long sum_small[MAXN+1][MAXN+1];
long long sum_big[MAXN+1][MAXN+1];
long long DP[MAXN+1];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// --- Đọc input ---
// Dạng: N (≤ 200), rồi A[1] A[2] ... A[N] (một hoán vị của 1..N)
cin >> N;
for(int i = 1; i <= N; i++){
cin >> A[i];
}
// Tính pos[v]
for(int i = 1; i <= N; i++){
pos[ A[i] ] = i;
}
// --- Tiền tính small_cnt[x][h] ---
// Với mọi 0 <= x < h <= N,
// small_cnt[x][h] = số i < pos[h] sao cho x < A[i] < h.
// Lưu ý: h chạy từ 1..N; x có thể = 0..h-1.
for(int x = 0; x <= N; x++){
for(int h = x+1; h <= N; h++){
int cnt = 0;
int ph = pos[h];
// đếm các i < ph
for(int i = 1; i < ph; i++){
if( A[i] > x && A[i] < h ){
cnt++;
}
}
small_cnt[x][h] = cnt;
}
}
// --- Tiền tính big_cnt[k][h] ---
// Với mọi 1 <= k <= N, 1 <= h <= k,
// big_cnt[k][h] = số i < pos[h] sao cho A[i] > k.
for(int k = 1; k <= N; k++){
for(int h = 1; h <= k; h++){
int cnt = 0;
int ph = pos[h];
for(int i = 1; i < ph; i++){
if( A[i] > k ){
cnt++;
}
}
big_cnt[k][h] = cnt;
}
}
// --- Xây prefix-sum sum_small và sum_big ---
// sum_small[x][t] = ∑_{h=1..t} small_cnt[x][h]
// sum_big[k][t] = ∑_{h=1..t} big_cnt[k][h]
for(int x = 0; x <= N; x++){
long long acc = 0;
for(int t = 1; t <= N; t++){
if(t <= x){
// small_cnt[x][t] định nghĩa chỉ khi t > x
// nếu t <= x, ta coi là 0
// (vì h phải > x để small_cnt[x][h] có nghĩa)
sum_small[x][t] = acc;
} else {
acc += small_cnt[x][t];
sum_small[x][t] = acc;
}
}
}
for(int k = 1; k <= N; k++){
long long acc = 0;
for(int t = 1; t <= N; t++){
if(t <= k){
acc += big_cnt[k][t];
}
sum_big[k][t] = acc;
}
}
// --- DP chính ---
// DP[0] = 0 (prefix rỗng, chưa xếp gì).
// DP[k] = min_{0 <= j < k} { DP[j] + cost_add(j→k) },
// với cost_add(j→k) = (sum_big[k][k] - sum_big[k][j])
// + (sum_small[j][k] - sum_small[j][j]).
//
// Giải thích:
// - sum_big[k][k] - sum_big[k][j] = ∑_{h = j+1..k} big_cnt[k][h].
// - sum_small[j][k] - sum_small[j][j] = ∑_{h = j+1..k} small_cnt[j][h].
//
// DP tính tuần tự k = 1..N.
const long long INF = (long long)1e18;
for(int k = 0; k <= N; k++){
DP[k] = INF;
}
DP[0] = 0;
for(int k = 1; k <= N; k++){
// Tính DP[k]
for(int j = 0; j < k; j++){
// cost_add(j→k):
long long part_big = sum_big[k][k] - sum_big[k][j];
long long part_small = sum_small[j][k] - sum_small[j][j];
long long cost_add = part_big + part_small;
long long cand = DP[j] + cost_add;
if(cand < DP[k]){
DP[k] = cand;
}
}
}
// Kết quả cuối cùng: DP[N]
cout << DP[N] << "\n";
return 0;
}
