题解 | 合唱队

#include<bits/stdc++.h>

using i128 = __int128;
using i64 = long long;
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const i64 inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

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> p(n, 1), s(n, 1);
  //预处理第l位的最长递增子序列的长度
	for(int l = 0; l < n; l++) {
		for(int r = 0; r < l; r++) {
			if (a[r] < a[l]) {
				p[l] = std::max(p[l], p[r] + 1);
			}
		}
	}
  //倒序处理最长递增子序列长度
	for(int l = n - 1; l >= 0; l--) {
		for(int r = n - 1; r > l; r--) {
			if (a[r] < a[l]) {
				s[l] = std::max(s[l], s[r] + 1);
			}
		}
	}
	int ans = 10 * n;
	for(int i = 1; i < n - 1; i++) {
	  //对于第i位，正向递增和反向递增之和就为总共有多少个但是多加了个第i位所以要减1
		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;
}