use std::collections::HashMap;

impl Solution {
    pub fn check_subarray_sum(nums: Vec<i32>, k: i32) -> bool {
        let mut map: HashMap<i32, i32> = HashMap::new();
        map.insert(0, -1);
        let mut sum = 0;
        for i in 0..nums.len() {
            sum += nums[i];
            let t = match k {
                0 => sum,
                _ => sum % k
            };
            if map.contains_key(&t) {
                if i as i32 - *map.get(&t).unwrap() > 1 {
                    return true;
                }
            } else {
                map.insert(t, i as i32);
            }
        }

        return false;
    }
}

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    fn dfs(root: Option<Rc<RefCell<TreeNode>>>,
           parent: Option<Rc<RefCell<TreeNode>>>, ans: &mut i32) -> (i32, i32) {
        if let Some(node) = root {
            let (mut incr, mut decr) = (0, 0);
            let l = Self::dfs(node.borrow().left.clone(), Some(node.clone()), ans);
            let r = Self::dfs(node.borrow().right.clone(), Some(node.clone()), ans);
            *ans = std::cmp::max(*ans, std::cmp::max(l.0 + r.1 + 1, l.1 + r.0 + 1));
            let p = parent.unwrap();
            if node.borrow().val == p.borrow().val + 1 {
                incr = std::cmp::max(l.0, r.0) + 1;
            }
            if node.borrow().val + 1 == p.borrow().val {
                decr = std::cmp::max(l.1, r.1) + 1;
            }
            return (incr, decr);
        } else {
            return (0, 0);
        }
    }

    pub fn longest_consecutive(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut ans = 0;
        Self::dfs(root.clone(), root.clone(), &mut ans);
        return ans;
    }
}

impl Solution {
    fn next_permutation(nums: Vec<i32>) -> Option<Vec<i32>> {
        let mut nums = nums;
        let mut i = nums.len() - 1;
        while i > 0 {
            i -= 1;
            if nums[i] < nums[i + 1] {
                let mut j = nums.len() - 1;
                while nums[i] >= nums[j] {
                    j -= 1;
                }
                nums.swap(i, j);

                let mut low = i + 1;
                let mut high = nums.len() - 1;

                while low < high {
                    nums.swap(low, high);
                    low += 1;
                    high -= 1;
                }
                return Some(nums);
            }
        }
        None
    }
    pub fn next_greater_element(n: i32) -> i32 {
        let mut n = n;
        let mut digits = vec![];
        while n != 0 {
            digits.push(n % 10);

            n = n / 10;
        }
        digits.reverse();
        if let Some(greater) = Self::next_permutation(digits) {
            let mut res = 0_i32;
            for n in greater {
                let (shift_res, is_overflow) = res.overflowing_mul(10);
                if is_overflow {
                    return -1;
                }
                let (new_res, is_overflow) = shift_res.overflowing_add(n);
                if is_overflow {
                    return -1;
                }
                res = new_res;
            }
            return res
        }
        -1
    }
}