题解 | #合唱队#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    let n = await readline();
    let datas = await readline();
    datas = datas.split(" ").map((data) => parseInt(data));
    if (datas.length != n || datas.length < 3) return;
    let removeNum = main(datas);
    console.log(removeNum);
})();


// function getIncrean(datas) {
//     let maxNum = getMaxNum(datas);
//     let matrix = [];
//     // 初始化
//     for (let i = 0; i < datas.length; i++) {
//         matrix[i] = [];
//         for (let j = 0; j <= maxNum; j++) {
//             matrix[i][j] = 0;
//         }
//     }
//     // 从左到右 最长递增数列
//     for (let i = 1; i < datas.length; i++) {
//         let num = datas[i - 1];
//         for (let j = 0; j <= maxNum; j++) {
//             if (j < num) {
//                 matrix[i][j] = matrix[i - 1][j];
//             } else {
//                 matrix[i][j] = Math.max(
//                     1 + matrix[i - 1][num !== 0 ? num - 1 : 0],
//                     matrix[i - 1][j]
//                 );
//             }
//         }
//     }
//     return matrix;
// }


function getIncrean(datas) {
    let list = []
    for (let i = 0; i < datas.length; i++) {
        list[i] = 1;
        for (let j = 0; j < i; j++) {
            if( datas[i] > datas[j]){
                list[i] = Math.max(list[i], list[j] + 1)
            }
        }
    }
    return list;
}

function main(datas) {

    let lmatrix = getIncrean(datas);
    // 从右到左， 最长递增数列
    datas.reverse();
    let rmatrix = getIncrean(datas);

    // 计算最长合唱队
    datas.reverse();
    let max = 0;
    for (let i = 2; i < datas.length; i++) {
        const ll = lmatrix[i - 1];
        const rl = rmatrix[datas.length - i]
         let val = ll + rl - 1;
        if (val > max) {
            max = val
        }
    }
    return datas.length - max;
}

function getMaxNum(datas) {
    if (!datas || !datas.length) {
        return;
    }
    let max = datas[0];
    for (let i = 1; i < datas.length; i++) {
        if (max < datas[i]) {
            max = datas[i];
        }
    }
    return max;
}