题解 | #合唱队形#

#include<iostream>
using namespace std;
#define N 105

int arr[N];  //从左往右的最大递增子序列
int dp1[N];  //从右往左的最大递增子序列
int dp2[N];


int main() {
    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        for (int i = 0; i < n; i++) {
            dp1[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp1[i] = max(dp1[i], dp1[j] + 1);
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            dp2[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (arr[j] < arr[i])
                    dp2[i] = max(dp2[i], dp2[j] + 1);

            }
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (dp1[i] + dp2[i] > max)
                max = dp1[i] + dp2[i];
        }


        cout << n - max + 1 << endl;
    }
}