特判 $a$ 升序的情况。然后一定会交换一对逆序对。

设交换 $(i, j)$，其中 $i < j$ 且 $a_i > a_j$。那么会使逆序对减少 $\sum\limits_{k = i + 1}^{j - 1} [a_j \le a_k < a_i] + [a_j < a_k \le a_i]$。由于涉及多维偏序，贡献不好拆开。

观察一下，若 $i_1 < i_2$ 且 $a_{i_1} \ge a_{i_2}$，那么选择 $i_1$ 一定不劣。类似地若 $j_1 > j_2$ 且 $a_{j_1} \le a_{j_2}$ 那么选择 $j_1$ 一定不劣。

所以选择的 $i$ 一定是前缀最大值，$j$ 一定是后缀最小值。

设前缀最大值位置为 $b_1, b_2, \ldots, b_{m_1}$，后缀最小值位置为 $c_1, c_2, \ldots, c_{m_2}$，那么一个 $k$ 对 $(b_i, c_j)$ 的贡献形如若 $i \in [l_1, r_1], j \in [l_2, r_2]$ 则令 $f_{i, j}$ 加上 $1$（这里找左右端点可以二分）。最后求所有 $f_{i, j}$ 的最大值。可以扫描线 + 线段树解决。

时间复杂度 $O(n \log n)$。

:::info[代码]

// Problem: P15810 [JOI 2013 Final] 冒泡排序 / Bubble Sort
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P15810
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int maxn = 100100;

int n, a[maxn], b[maxn], c[maxn], m1, m2, lsh[maxn], tot;

struct line {
	int l, r, x;
	line(int _l = 0, int _r = 0, int _x = 0) : l(_l), r(_r), x(_x) {}
};

vector<line> md[maxn];

namespace BIT {
	int c[maxn];
	
	inline void update(int x, int d) {
		for (int i = x; i <= tot; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
}

namespace SGT {
	int a[maxn << 2], tag[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = max(a[x << 1], a[x << 1 | 1]);
	}
	
	inline void pushtag(int x, int y) {
		a[x] += y;
		tag[x] += y;
	}
	
	inline void pushdown(int x) {
		if (!tag[x]) {
			return;
		}
		pushtag(x << 1, tag[x]);
		pushtag(x << 1 | 1, tag[x]);
		tag[x] = 0;
	}
	
	void update(int rt, int l, int r, int ql, int qr, int x) {
		if (ql <= l && r <= qr) {
			pushtag(rt, x);
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
}

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		lsh[++tot] = a[i];
	}
	if (is_sorted(a + 1, a + n + 1)) {
		bool fl = 0;
		for (int i = 1; i < n; ++i) {
			fl |= (a[i] == a[i + 1]);
		}
		puts(fl ? "0" : "1");
		return;
	}
	sort(lsh + 1, lsh + tot + 1);
	tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	for (int i = 1; i <= n; ++i) {
		a[i] = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
	}
	ll ans = 0;
	for (int i = n; i; --i) {
		ans += BIT::query(a[i] - 1);
		BIT::update(a[i], 1);
	}
	int mx = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i] > mx) {
			mx = a[i];
			b[++m1] = i;
		}
	}
	int mn = 2e9;
	for (int i = n; i; --i) {
		if (a[i] < mn) {
			mn = a[i];
			c[++m2] = i;
		}
	}
	reverse(c + 1, c + m2 + 1);
	for (int i = 1; i <= n; ++i) {
		int l = 1, r = m1, p1 = m1 + 1, p2 = 0, p3 = m2 + 1, p4 = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (a[b[mid]] >= a[i]) {
				p1 = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		l = 1;
		r = m1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (b[mid] < i) {
				p2 = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		if (p1 > p2) {
			continue;
		}
		l = 1;
		r = m2;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (i < c[mid]) {
				p3 = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		l = 1;
		r = m2;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (a[i] > a[c[mid]]) {
				p4 = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		if (p3 > p4) {
			continue;
		}
		md[p1].pb(p3, p4, 1);
		md[p2 + 1].pb(p3, p4, -1);
	}
	for (int i = 1; i <= n; ++i) {
		int l = 1, r = m1, p1 = m1 + 1, p2 = 0, p3 = m2 + 1, p4 = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (a[b[mid]] > a[i]) {
				p1 = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		l = 1;
		r = m1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (b[mid] < i) {
				p2 = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		if (p1 > p2) {
			continue;
		}
		l = 1;
		r = m2;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (i < c[mid]) {
				p3 = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		l = 1;
		r = m2;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (a[i] >= a[c[mid]]) {
				p4 = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		if (p3 > p4) {
			continue;
		}
		md[p1].pb(p3, p4, 1);
		md[p2 + 1].pb(p3, p4, -1);
	}
	mx = 0;
	for (int i = 1; i <= m1; ++i) {
		for (line u : md[i]) {
			SGT::update(1, 1, m2, u.l, u.r, u.x);
		}
		mx = max(mx, SGT::a[1]);
	}
	printf("%lld\n", ans - mx - 1);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

:::info