fn dominator(a: &[i64]) -> i64 {
    let mut size = 0i64;
    let mut value = 0;
    let mut index: i64 = 0;

    for (k, &v) in a.iter().enumerate() {
        if size == 0 {
            size += 1;
            value = v;
            index = k as i64;
        } else if value != v {
            size -= 1;
        } else {
            size += 1;
        }
    }

    let candidate = if size > 0 { value } else { -1 };

    let count = a.iter().filter(|&&v| v == candidate).count() as i64;
    if count <= a.len() as i64 / 2 {
        index = -1;
    }

    index
}

fn equi_leader(a: &[i64]) -> i64 {
    let mut leader_size = 0i64;
    let mut value = 0;
    for &v in a {
        if leader_size == 0 {
            leader_size += 1;
            value = v;
        } else if value != v {
            leader_size -= 1;
        } else {
            leader_size += 1;
        }
    }
    let candidate = if leader_size > 0 { value } else { -1 };

    let leader_count = a.iter().filter(|&&v| v == candidate).count() as i64;
    let leader = if leader_count > a.len() as i64 / 2 { candidate } else { -1 };

    let count = a.len() as i64;
    let mut l_leader_count = 0i64;
    let mut equi_leaders = 0i64;

    for (k, &v) in a.iter().enumerate() {
        let k = k as i64;
        let left_half = (k + 1) / 2;
        let right_half = (count - k - 1) / 2;
        if v == leader {
            l_leader_count += 1;
        }

        let r_leader_count = leader_count - l_leader_count;
        if l_leader_count > left_half && r_leader_count > right_half {
            equi_leaders += 1;
        }
    }

    equi_leaders
}

use std::collections::VecDeque;

fn fib_frog(a: &[i64]) -> i64 {
    let size = a.len() as i64;

    let mut fib = vec![0i64, 1];
    let mut i = 1;
    while fib[i] <= size {
        i += 1;
        fib.push(fib[i - 1] + fib[i - 2]);
    }

    let mut paths: VecDeque<(i64, i64)> = VecDeque::new();
    paths.push_back((-1, 0));

    let mut steps = vec![false; size as usize];

    while let Some((idx, jmp)) = paths.pop_front() {
        for f in (2..fib.len()).rev() {
            let next_idx = idx + fib[f];
            if next_idx == size {
                return jmp + 1;
            }
            if next_idx > size || steps[next_idx as usize] || a[next_idx as usize] == 0 {
                continue;
            }
            if a[next_idx as usize] == 1 {
                steps[next_idx as usize] = true;
                paths.push_back((next_idx, jmp + 1));
            }
        }
    }

    -1
}

fn fish(a: &[i64], b: &[i64]) -> i64 {
    let size = a.len();
    let mut dead = 0i64;
    let mut fish: Vec<i64> = Vec::new();

    for i in 0..size {
        if b[i] == 1 {
            fish.push(a[i]);
        } else if !fish.is_empty() {
            while let Some(&last) = fish.last() {
                dead += 1;
                if a[i] > last {
                    fish.pop();
                } else {
                    break;
                }
            }
        }
    }

    size as i64 - dead
}

fn flags(a: &[i64]) -> i64 {
    let size = a.len();
    let mut peaks = vec![false; size];
    for i in 1..size {
        let next = a.get(i + 1).copied().unwrap_or(0);
        peaks[i] = a[i - 1] < a[i] && a[i] > next;
    }

    let mut next_peak = vec![-1i64; size];
    if size > 0 {
        next_peak[size - 1] = -1;
        for i in (0..size - 1).rev() {
            next_peak[i] = if peaks[i] { i as i64 } else { next_peak[i + 1] };
        }
    }

    let mut i = 1i64;
    let mut result = 0i64;
    while i * (i - 1) <= size as i64 {
        let mut pos = 0i64;
        let mut num = 0i64;
        while pos < size as i64 && num < i {
            pos = next_peak[pos as usize];
            if pos == -1 {
                break;
            }
            num += 1;
            pos += i;
        }
        i += 1;
        result = result.max(num);
    }

    result
}

fn frog_jmp(x: i64, y: i64, d: i64) -> i64 {
    let dist = y - x;
    (dist + d - 1) / d
}

use std::collections::HashSet;

fn frog_river_one(x: i64, a: &[i64]) -> i64 {
    let mut existing: HashSet<i64> = HashSet::new();
    for (k, &i) in a.iter().enumerate() {
        if i <= x && existing.insert(i) && existing.len() as i64 == x {
            return k as i64;
        }
    }

    -1
}

fn genomic_range_query(s: &str, p: &[usize], q: &[usize]) -> Vec<i64> {
    let chars: Vec<char> = s.chars().collect();
    p.iter()
        .zip(q.iter())
        .map(|(&pi, &qi)| {
            let sub = &chars[pi..=qi];
            if sub.contains(&'A') {
                1
            } else if sub.contains(&'C') {
                2
            } else if sub.contains(&'G') {
                3
            } else {
                4
            }
        })
        .collect()
}

fn is_ipv_4_adress(input_string: &str) -> bool {
    let parts: Vec<&str> = input_string.split('.').collect();
    if parts.len() != 4 {
        return false;
    }

    for part in &parts {
        match part.parse::<i64>() {
            Ok(n) => {
                if n > 255 || part.to_string() != n.to_string() {
                    return false;
                }
            }
            Err(_) => return false,
        }
    }

    true
}

fn ladder(a: &[i64], b: &[i64]) -> Vec<i64> {
    let size = a.len();
    let mut r = vec![0i64; size];

    let max_b = *b.iter().max().unwrap();
    let mod_mask = (1i64 << max_b) - 1;

    let max_a = *a.iter().max().unwrap();
    let mut fib = vec![0i64, 1];
    for i in 2..(max_a as usize + 2) {
        fib.push((fib[i - 1] + fib[i - 2]) & mod_mask);
    }

    for i in 0..size {
        r[i] = fib[(a[i] + 1) as usize] & ((1i64 << b[i]) - 1);
    }

    r
}