题目描述

位同学站成一排，音乐老师要请其中的位同学出列，使得剩下的位同学排成合唱队形。

合唱队形是指这样的一种队形：设 位同学从左到右依次编号为，他们的身高分别为，则他们的身高满足$T_1 < T_2 < … < T_i \ \ $, 。

你的任务是，已知所有位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入

输入的第一行是一个整数（），表示同学的总数。第二行有个整数，用空格分隔，第个整数（）是第 位同学的身高（厘米）。

输出

输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

样例

输入样例

8
186 186 150 200 160 130 197 220

输出样例

4

提示

对于50%的数据，保证有 ；

对于100%的数据，保证有 。

源代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int a[200], b[200], c[200];
    int n, i, j, maxx;
    cin >> n;
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    for (i = 1; i <= n; i++) cin >> a[i];  //同学的身高
    for (i = 1; i <= n; i++)               //按照从左向右的顺序计算
    {
        b[i] = 1;
        for (j = 1; j <= i - 1; j++)
            if (a[i] > a[j] && b[j] + 1 > b[i]) b[i] = b[j] + 1;
    }
    for (i = n; i >= 1; i--)  //按照从右向左的顺序计算
    {
        c[i] = 1;
        for (j = i + 1; j <= n; j++)
            if (a[i] > a[j] && c[j] + 1 > c[i]) c[i] = c[j] + 1;
    }
    maxx = 0;  //计算合唱队的人数max其中一个人被重复计算！
    for (i = 1; i <= n; i++)
        if (b[i] + c[i] > maxx) maxx = b[i] + c[i];
    cout << n - maxx + 1 << endl;
}