impl Solution {
    fn find(x : usize, uf: &mut Vec<usize>) ->usize {
        if x == uf[x as usize] {
            return x;
        } else {
            uf[x] = Self::find(uf[x], uf);
            return uf[x];
        }
    }

    pub fn min_cost_to_supply_water(n: i32, wells: Vec<i32>, pipes: Vec<Vec<i32>>) -> i32 {
        let mut uf = vec![0; n as usize + 1];
        for i in 0..n + 1 {
            uf[i as usize] = i as usize;
        }
        let mut p = pipes;
        for i in 0..n {
            p.push(vec![0, i + 1, wells[i as usize]]);
        }
        p.sort_by_key(|x| x[2]);
        let mut ans = 0;
        for pipe in p {
            let (fx, fy) = (Self::find(pipe[0] as usize, &mut uf),
                                        Self::find(pipe[1] as usize, &mut uf));
            if fx == fy {
                continue;
            }
            ans += pipe[2];
            uf[fx] = fy;
        }
        return ans;
    }
}

impl Solution {
    fn compute_frequency(s: &String) ->i32 {
        let mut min_char = std::i32::MAX;
        let mut ans = 0;
        for c in s.chars() {
            if (c as i32) < min_char {
                min_char = c as i32;
            }
        }
        for i in 0..s.len() {
            if s.bytes().nth(i).unwrap() as i32 == min_char {
                ans += 1;
            }
        }
        return ans;
    }

    pub fn num_smaller_by_frequency(queries: Vec<String>, words: Vec<String>) -> Vec<i32> {
        let (mut ans, mut cnt) = (vec![], vec![0; 11]);
        for w in &words {
            let mut i = Self::compute_frequency(w) - 1;
            while i >= 0 {
                cnt[i as usize] += 1;
                i -= 1;
            }
        }
        for q in &queries {
            let val = Self::compute_frequency(q);
            ans.push(cnt[val as usize]);
        }
        return ans;
    }
}

use std::collections::HashMap;

impl Solution {
    fn get_pos(indices: &Vec<i32>, target: i32) ->usize {
        let size = indices.len();
        let index = match indices.binary_search(&target) {
            Ok(i) => i,
            Err(i) => i,
        };

        if index == 0 {
            return indices[0] as usize;
        }
        if index == size {
            return indices[size - 1] as usize;
        }
        if indices[index] - target < target - indices[index - 1] {
            return indices[index] as usize;
        } else {
            return indices[index - 1] as usize;
        }
    }

    pub fn shortest_distance_color(colors: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let mut map : HashMap<i32, Vec<i32>> = HashMap::new();
        let mut res = vec![];
        for i in 0..colors.len() {
            let color = colors[i];
            if !map.contains_key(&color) {
                map.insert(color, vec![i as i32]);
            } else {
                let mut val = (*map.get(&color).unwrap()).clone();
                val.push(i as i32);
                map.insert(color, val);
            }
        }

        for q in queries {
            let target = q[0];
            if !map.contains_key(&q[1]) {
                res.push(-1);
                continue;
            }
            let pos = Self::get_pos(map.get(&q[1]).unwrap(), target);
            res.push((pos as i32 - target).abs());
        }

        return res;
    }
}