数据究竟有多水

#include<bits/stdc++.h>

using namespace std;

int n;
int arr[10000000];
int dp[10000000];

int main()
{
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", arr+i);
	
	int maxx = 0;
	for(int j=2; j<=n; j++)
	{
		int tmp = 0;
		
		int len = 1;
		dp[1] = arr[1];
		for(int i=2; i<=j-1; i++)
		{
			int t = lower_bound(dp+1, dp+len+1, arr[i])-dp;
			dp[t] = arr[i];
			if(len < t) len++;
		}
		
		tmp += len;
		
		memset(dp, 0, sizeof(dp));
		
		len = 1;
		dp[1] = arr[j];
		for(int i=j; i<=n; i++)
		{
			int t = lower_bound(dp+1, dp+len+1, arr[i], greater<int>())-dp;
			dp[t] = arr[i];
			if(len < t) len++;
		}
		
		tmp += len;
		
		maxx = max(tmp, maxx);
	}
	
	printf("%d", n-maxx);
	
	return 0;
}