trait SliceExt<T> {
    fn split_by<F>(&self, pred: F) -> (&[T], &[T])
    where
        F: FnMut(&T) -> bool;
}

impl<T> SliceExt<T> for [T] {
    fn split_by<F>(&self, mut pred: F) -> (&[T], &[T])
    where
        F: FnMut(&T) -> bool,
    {
        let p = self
            .iter()
            .enumerate()
            .find(|&(_, val)| !pred(val))
            .map(|(pos, _)| pos)
            .unwrap_or_else(|| self.len());

        self.split_at(p)
    }
}

#[test]
fn test_split_by() {
    assert!([].split_by(|x: &i32| *x < 10) == (&[], &[]));
    assert!([1].split_by(|&x| x < 10) == (&[1], &[]));
    assert!([1, 11].split_by(|&x| x < 10) == (&[1], &[11]));
    assert!([1, 2, 10, 11].split_by(|&x| x < 10) == (&[1, 2], &[10, 11]));
    assert!([11].split_by(|&x| x < 10) == (&[], &[11]));
}

fn check_bst(v: &[u32]) -> bool {
    if v.len() < 2 {
        return true;
    }

    let first = v[0];
    let (left, right) = &v[1..].split_by(|&val| val <= first);

    if right.iter().any(|&x| x < first) {
        return false;
    }

    check_bst(left) && check_bst(right)
}

fn main() {
    assert!(check_bst(&[]));
    assert!(check_bst(&[3]));
    assert!(check_bst(&[3, 1, 2]));
    assert!(check_bst(&[3, 2, 1, 4]));
    assert!(check_bst(&[3, 4]));
    assert!(!check_bst(&[3, 4, 1, 2]));
}