合唱队形

两次DP求最长递增子序列，然后，结果是

// runtime: 3ms
// space: 496K
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 100;

int arr1[MAX];

int arr2[MAX]; // reversal of arr1

int dp1[MAX]; // arr1 max increase subsequence

int dp2[MAX]; // arr2 max increase subsequence

void MaxIncSequence(int* arr, int* dp, int n) {
    for (int i = 0; i < n; ++i) {
        dp[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

void Print(int n) {
    int answer = n;
    for (int i = 0; i < n; ++i) {
        answer = min(answer, n - dp1[i] - dp2[n - 1 -i] + 1);
    }
    printf("%d\n", answer);
}

int main() {
    int n;
    while (cin>> n) {
        for (int i = 0; i < n; ++i) {
            cin>> arr1[i];
            arr2[n - 1 - i] = arr1[i];
        }
        MaxIncSequence(arr1, dp1, n);
        MaxIncSequence(arr2, dp2, n);
        Print(n);
    }
    return 0;
}