题解 | #合唱队#

import java.util.Arrays; import java.util.Scanner;

public class Main {

public static void main(String[] args) {
	// TODO Auto-generated method stub

	Scanner sc = new Scanner(System.in);
	while (sc.hasNextLine()) {
		int number = Integer.parseInt(sc.nextLine());
		String str = sc.nextLine();
		String[] strArr = str.split(" ");
		
		// 解题思想
		// 分别计算某一个位置左边最长递增子序列和右边最长递减子序列

		int[] dp1 = new int[number];
		Arrays.fill(dp1, 1);
		for (int i = 0; i < number; i++) {
			for (int j = 0; j < i; j++) {
				int iValue = Integer.parseInt(strArr[i]);
				int beforeValue = Integer.parseInt(strArr[j]);
				if(iValue > beforeValue) {
					// 这里注意一定要取max，不能直接用dp1[j]+1
					// 因为循环每次都会dp1[i]都会被赋值 比如遇到1 2 5 2 6 4 这种序列
					// 当循环到i=3时，只有前面只有数值1小于2，所以dp1[3]= 1+1=2;
					// 当循环到i=4时，只有前面只有数值1/2/5小于6，所以dp1[4]=3+1 =4;
					// 如果不取max直接取dp1[j]+1，那么dp1[4]=3与实际不符
					dp1[i] = Math.max(dp1[i], dp1[j]+1);
				}
			}
		}
		
		// 此处注意一定要倒序循环
		int[] dp2 = new int[number];
		Arrays.fill(dp2, 1);
		for (int i = number-1; i >=0; i--) {
			for (int j =number-1; j > i; j--) {
				int iValue = Integer.parseInt(strArr[i]);
				int beforeValue = Integer.parseInt(strArr[j]);
				if(iValue > beforeValue) {
					dp2[i] = Math.max(dp2[i], dp2[j]+1);
				}
			}
		}
		
		int max = 0;
		for (int i = 0; i < number; i++) {
			max = Math.max(max,(dp1[i]+dp2[i]-1));
		}
		int needRemove = number - max;
		System.out.println(needRemove);
	}
}

}