题解 | 合唱队形

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> inc(n, 1), dec(n, 1);
    // LIS ending at i (strictly increasing)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i]) inc[i] = max(inc[i], inc[j] + 1);

    // LDS starting at i (strictly decreasing to the right)
    for (int i = n - 1; i >= 0; --i)
        for (int j = n - 1; j > i; --j)
            if (a[j] < a[i]) dec[i] = max(dec[i], dec[j] + 1);

    int best = 0;
    for (int i = 0; i < n; ++i) best = max(best, inc[i] + dec[i] - 1);

    cout << (n - best) << '\n';
    return 0;
}