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

impl Solution {
    pub fn max_level_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let (mut ans, mut sum, mut level) = (0, std::i32::MIN, 1);
        if root.is_none() {
            return ans;
        }

        let mut q = VecDeque::new();
        q.push_back(root.clone());

        while !q.is_empty() {
            let (mut size, mut cur_sum) = (q.len(), 0);
            while size != 0 {
                if let Some(node) = q.pop_front() {
                    cur_sum += node.clone().unwrap().borrow().val;
                    let (left, right) = (
                        node.clone().unwrap().borrow().left.clone(),
                        node.clone().unwrap().borrow().right.clone()
                    );
                    if !left.is_none() {
                        q.push_back(left);
                    }
                    if !right.is_none() {
                        q.push_back(right);
                    }
                }
                size -= 1;
            }
            if cur_sum > sum {
                sum = cur_sum;
                ans = level;
            }
            level += 1;
        }
        return ans;
    }
}

use std::collections::HashMap;

impl Solution {
    pub fn calculate_time(keyboard: String, word: String) -> i32 {
        let mut map = HashMap::new();
        for i in 0..26 {
            map.insert(keyboard.chars().nth(i).unwrap(), i);
        }

        let (mut ans, size) = (0, word.len());
        if size == 1 {
            return ans;
        }
        
        for i in 0..size {
            let ci = word.chars().nth(i).unwrap();
            if i == 0 {
                ans += *map.get(&ci).unwrap() as i32;
                continue;
            }
            let cii = word.chars().nth(i - 1).unwrap();
            ans += (*map.get(&cii).unwrap() as i32
                - *map.get(&ci).unwrap() as i32).abs();
        }
        return ans;
    }
}

use std::collections::BinaryHeap;

impl Solution {
    pub fn connect_sticks(sticks: Vec<i32>) -> i32 {
        let (mut heap, mut ans) = (BinaryHeap::new(), 0);
        for stick in sticks {
            heap.push(stick * -1);
        }
        while heap.len() > 1 {
            let (a, b) = (heap.pop().unwrap() * -1, heap.pop().unwrap() * -1);
            ans += a + b;
            heap.push((a + b) * -1);
        }
        return ans;
    }
}