线段树求解

#include <bits/stdc++.h>

using i64 = long long;
#define endl '\n'
const i64 inf = 1e17 + 50, mod = 1e9 + 7;

class SegmentTree {
private:
	int size;
	std::vector<int> tree;

public:
	SegmentTree(int max_val) {
		size = 1;
		while (size < max_val) size <<= 1;
		tree.assign(2 * size, 0);
	}

	void update(int pos, int val) {
		int node = size + pos - 1;
		if (tree[node] >= val) return;
		tree[node] = val;
		for(node >>= 1; node >= 1; node >>= 1) {
			int new_val = std::max(tree[2 * node], tree[2 * node + 1]);
			if (tree[node] == new_val) break;
			tree[node] = new_val;
		}
	}

	int query(int l, int r) {
		if (l > r) return 0;
		l = std::max(l, 1);
		r = std::min(r, size);
		int res = 0;
		int node_l = size + l - 1;
		int node_r = size + r - 1;
		while (node_l <= node_r) {
			if (node_l % 2 == 1) res = std::max(res, tree[node_l++]);
			if (node_r % 2 == 0) res = std::max(res, tree[node_r--]);
			node_l >>= 1;
			node_r >>= 1;
		}
		return res;
	}
};

void solve() {
	int n;
	std::cin >> n;
	std::vector<int> a(n);
	for(int i = 0; i < n; ++i) std::cin >> a[i];

	// 离散化
	std::vector<int> b(a);
	std::sort(b.begin(), b.end());
	b.erase(std::unique(b.begin(), b.end()), b.end());
	for(int &x : a) {
		x = std::lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
	}
	int m = b.size();

	// 计算前缀数组p
	std::vector<int> p(n, 1);
	SegmentTree st_p(m);
	for(int i = 0; i < n; ++i) {
		int x = a[i];
		p[i] = st_p.query(1, x - 1) + 1;
		st_p.update(x, p[i]);
	}

	// 计算后缀数组s
	std::vector<int> s(n, 1);
	SegmentTree st_s(m);
	for(int i = n - 1; i >= 0; --i) {
		int x = a[i];
		s[i] = st_s.query(1, x - 1) + 1;
		st_s.update(x, s[i]);
	}

	int ans = 10 * n;
	for(int i = 1; i < n - 1; ++i) {
		ans = std::min(ans, n - (p[i] + s[i] - 1));
	}
	std::cout << ans << endl;
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	solve();
	return 0;
}