use std::io::*; mod fenwick_tree { use std::ops::*; pub struct FenwickTree { data: Vec, identity: T, operation: F, } impl T> FenwickTree { pub fn new(size: usize, id: T, op: F) -> FenwickTree { FenwickTree { data: vec![id; size + 1], identity: id, operation: op, } } pub fn query(&self, i: usize) -> T { let mut res = self.identity; let mut idx = i as isize - 1; while idx >= 0 { res = (self.operation)(res, self.data[idx as usize]); idx = (idx & (idx + 1)) - 1; } res } pub fn update(&mut self, i: usize, x: T) { let mut idx = i; while idx < self.data.len() { self.data[idx] = (self.operation)(self.data[idx], x); idx |= idx + 1; } } } } fn main() { let mut s: String = String::new(); std::io::stdin().read_to_string(&mut s).ok(); let mut itr = s.trim().split_whitespace(); let n: usize = itr.next().unwrap().parse().unwrap(); let mut a: Vec = (0..n) .map(|_| itr.next().unwrap().parse().unwrap()) .collect(); a.reverse(); let mut bit = fenwick_tree::FenwickTree::new(n, 0, std::cmp::max); for i in 0..n { bit.update(a[i], bit.query(a[i]) + 1); } println!("{}", n - bit.query(n + 1)); }