fn lower_bound<T: PartialOrd>(list: &Vec<T>, value: &T) -> usize {
    if list.is_empty() {
        return 0;
    }
    let mut lower = 0usize;
    let mut upper = list.len();
    while lower != upper {
        let middle = lower + upper >> 1;
        if list[middle] < *value {
            lower = middle + 1;
        } else {
            upper = middle;
        }
    }
    return lower;
}

fn lis<T: PartialOrd + Copy>(list: &Vec<T>) -> Vec<T> {
    if list.is_empty() {
        return Vec::new();
    }
    let mut subseq: Vec<T> = Vec::new();
    subseq.push(*list.first().unwrap());
    for i in list[1..].iter() {
        if *i <= *subseq.last().unwrap() {
            let index = lower_bound(&subseq, i);
            subseq[index] = *i;
        } else {
            subseq.push(*i);
        }
    }
    return subseq;
}

fn main() {
    let list = vec![3, 2, 6, 4, 5, 1];
    println!("{:?}", lis(&list));
    let list = vec![0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];
    println!("{:?}", lis(&list));
}