题解 | #合唱队#

// 以每一个人作为基准，寻找左边最长递增子序列，右边的也可以反转求值后再反转
// 求每个人为基准的最长左递增子序列长度集合

let n = Number(readline()), dp = []

let stu = readline().split(' ').map(i => Number(i))

let dp1 = fn(stu), dp2 = fn(stu.reverse()).reverse(), max = 1

for(let i=0; i<n; i++) {
    max = Math.max(max, dp1[i]+dp2[i])
}

console.log(n-max+1) // 基准元素两次参与计算，需要+1

function fn(arr) {
    let dp = [1] // 保存每个元素所在位置的左边最长递增子序列长度，左边第一个元素只有自己，所以是1
    for(let i=1; i<arr.length; i++) {
        dp[i] = 1 // 每个元素首先有个自己，初始化为1
        for(let j=0; j<i; j++) {
            if(arr[j] < arr[i]) { // 左边元素小于基准元素
                dp[i] = Math.max(dp[i], dp[j]+1) 
            }
        }
    }
    return dp
}



// 选中一个作为基准，划分的小问题就是，某个同学要不要出列
// l和r分别向左向右检索，发现小的就继续前进（判断前进或是加入out），发现大的就加入out

// 方案一：时间复杂度太大
// for(let i=0; i<n; i++) {
//     arr.push(fn(i, stu[i], i, stu[i], 0))
// }

// arr.sort((a, b) => a-b)

// console.log(arr[0])

// function fn(l, ln, r, rn, out) {
//     if(l==0 && r==stu.length)return out
//     if(l>0) {
//         if(stu[l-1]>=ln)return fn(l-1, ln, r, rn, out+1)
//         else return Math.min(fn(l-1, ln, r, rn, out+1), fn(l-1, stu[l-1], r, rn, out))
//     }
//     if(r<stu.length) {
//         if(stu[r+1]>=rn)return fn(l, ln, r+1, rn, out+1)
//         else return Math.min(fn(l, ln, r+1, rn, out+1), fn(l, ln, r+1, stu[r+1], out))
//     }
// }