impl Solution {
    pub fn knight_dialer(n: i32) -> i32 {
        const MOD : u64 = 1e9 as u64 + 7;
        const dirs: [(i32, i32); 8] = [(-2, -1), (-2, 1), (-1, -2), (-1, 2),
            (1, -2), (1, 2), (2, -1), (2, 1)];
        let mut dp = [[1; 3] ; 4];
        dp[3][0] = 0; dp[3][2] = 0;
        for k in 1..n {
            let mut tmp = [[0; 3] ; 4];
            for i in 0..4 {
                for j in 0..3 {
                    if i == 3 && j != 1 {
                        continue;
                    }
                    for d in 0..8 {
                        let (xx, yy) = (j + dirs[d].0, i + dirs[d].1);
                        if xx < 0 || yy < 0 || xx >= 3 || yy >= 4 {
                            continue;
                        }
                        tmp[i as usize][j as usize] = (tmp[i as usize][j as usize] +
                            dp[yy as usize][xx as usize]) % MOD;
                    }
                }
            }
            dp.swap_with_slice(&mut tmp[0..]);
        }

        let mut ans : i32 = 0;
        for i in 0..4 {
            for j in 0..3 {
                ans = ((ans as u64 + dp[i][j]) % MOD) as i32;
            }
        }
        return ans;
    }
}

impl Solution {
    pub fn longest_ones(a: Vec<i32>, k: i32) -> i32 {
        let (mut ans, mut zeros, mut sum) = (0, 0, 0);
        let mut i = 0;
        for j in 0..a.len() {
            if a[j] == 0 {
                zeros += 1;
            }
            while zeros > k {
                if a[i] == 0 {
                    zeros -= 1;
                }
                i += 1;
            }
            ans = std::cmp::max(ans, j - i + 1);
        }
        return ans as i32;
    }
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn compute(v: &Vec<i32>, start: i32, end: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if start > end {
            return None;
        }
        if start == end {
            let mut node = TreeNode::new(v[start as usize]);
            return  Some(Rc::new(RefCell::new(node)))
        }
        let (mut s, mut e) = (start + 1, start + 1);
        while e <= end {
            if v[e as usize] > v[start as usize] {
                break;
            }
            e += 1;
        }
        e -= 1;
        let mut node = TreeNode::new(v[start as usize]);
        node.left = Self::compute(v, s, e);
        node.right = Self::compute(v, e + 1, end);
        Some(Rc::new(RefCell::new(node)))
    }
    pub fn bst_from_preorder(preorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        return Self::compute(&preorder, 0, preorder.len() as i32 - 1);
    }
}