题解 | #合唱队#

use std::io::{self, *};

fn maxLeft(q: &Vec<usize>, res: &mut Vec<usize>) {
    let mut temp = vec![usize::MAX; q.len()];
    let mut pos = 0;
    for i in q {
        match temp.as_slice().binary_search(i) {
            Ok(p) => pos = p,
            Err(p) => pos = p,
        }
        temp[pos] = *i;
        res.push(pos)
    }
}

fn main() {
    let stdin = io::stdin();
    let mut line = String::new();
    stdin.read_line(&mut line);
    let n = line.trim().parse::<usize>().unwrap();
    line.clear();
    stdin.read_line(&mut line);
    let mut q: Vec<usize> = line.split(" ").map(|i| i.trim().parse::<usize>().unwrap()).collect();
    let mut ml = vec![];
    let mut mr = vec![];

    maxLeft(&q, &mut ml);

    q.reverse();
    maxLeft(&q, &mut mr);
    mr.reverse();
    let max = mr.iter().zip(ml.iter()).max_by_key(|i| *(i.0) + *(i.1)).unwrap();
    println!("{}", n - max.0 - max.1 - 1)
}