[NOIP2004]合唱队形

#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0, a[105], maxn[105], minn[105];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		maxn[i] = 1;
		minn[i] = 1;//读入与初始化
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			if (a[i] > a[j])
				maxn[i] = max(maxn[i], maxn[j] + 1);
  //从小到大寻找最长严格上升子序列
	for (int i = n; i >= 1; i--)
		for (int j = n; j >= i; j--)
			if (a[i] > a[j])
				minn[i] = max(minn[i], minn[j] + 1);
  //从大到小寻找最长严格下降子序列
	for (int i = 1; i <= n; i++) {
		cnt = max(cnt, maxn[i] + minn[i]);//遍历一遍，找到两端最长的点
	}
	cout << n - cnt + 1;//cnt里包含了两个分界点，多减去一个重复的
  
//	for (int i : maxn)
//		printf("%d ", i);
//	puts("");
//	for (int i : minn)
//		printf("%d ", i);
	return 0;
}