fn number_of_disc_intersections(a: &[i64]) -> i64 {
    let c = a.len();
    let mut start = vec![0i64; c];
    let mut end = vec![0i64; c];

    for (k, &v) in a.iter().enumerate() {
        let k = k as i64;
        let key = if k < v { 0 } else { (k - v) as usize };
        start[key] += 1;

        let key = if k + v >= c as i64 { c - 1 } else { (k + v) as usize };
        end[key] += 1;
    }

    let mut sum = 0i64;
    let mut active = 0i64;
    for k in 0..c {
        sum += active * start[k] + (start[k] * (start[k] - 1)) / 2;
        active += start[k] - end[k];
        if sum > 10_000_000 {
            return -1;
        }
    }

    sum
}

use std::collections::HashMap;

fn odd_occurrences_in_array(a: &[i64]) -> Option<i64> {
    let mut count: HashMap<i64, bool> = HashMap::new();
    for &value in a {
        if count.contains_key(&value) {
            count.remove(&value);
        } else {
            count.insert(value, true);
        }
    }

    count.keys().next().copied()
}

use std::collections::HashMap;

fn palindrome_rearranging(input_string: &str) -> bool {
    let mut counts: HashMap<char, i64> = HashMap::new();
    for c in input_string.chars() {
        *counts.entry(c).or_insert(0) += 1;
    }

    counts.values().filter(|&&v| v % 2 != 0).count() <= 1
}

fn passing_cars(a: &[i64]) -> i64 {
    let mut passing_cars = 0i64;
    let mut multiply = 0i64;
    for &i in a {
        if i == 0 {
            multiply += 1;
        } else if multiply > 0 {
            passing_cars += multiply;
            if passing_cars > 1_000_000_000 {
                return -1;
            }
        }
    }

    passing_cars
}

fn peaks(a: &[i64]) -> i64 {
    let n = a.len();
    if n <= 2 {
        return 0;
    }

    let mut sum = vec![0i64; n];
    let mut last: i64 = -1;
    let mut dist: i64 = 0;

    for i in 1..n - 1 {
        sum[i] = sum[i - 1];
        if a[i] > a[i - 1] && a[i] > a[i + 1] {
            dist = dist.max(i as i64 - last);
            last = i as i64;
            sum[i] += 1;
        }
    }

    sum[n - 1] = sum[n - 2];
    if sum[n - 1] == 0 {
        return 0;
    }

    dist = dist.max(n as i64 - last);

    let mut i = (dist >> 1) + 1;
    while i < dist {
        if n as i64 % i == 0 {
            let mut last_sum = 0i64;
            let mut j = i;
            while j <= n as i64 {
                if sum[(j - 1) as usize] <= last_sum {
                    break;
                }
                last_sum = sum[(j - 1) as usize];
                j += i;
            }
            if j > n as i64 {
                return n as i64 / i;
            }
        }
        i += 1;
    }

    let mut last_final = dist;
    while n as i64 % last_final != 0 {
        last_final += 1;
    }

    n as i64 / last_final
}

fn perm_check(mut a: Vec<i64>) -> i64 {
    a.sort();

    for (k, &i) in a.iter().enumerate() {
        if k + 1 < a.len() && i != k as i64 + 1 {
            return 0;
        }
    }

    1
}

fn perm_missing_element(mut a: Vec<i64>) -> i64 {
    a.sort();

    for (k, &v) in a.iter().enumerate() {
        if v != k as i64 + 1 {
            return k as i64 + 1;
        }
    }

    a.len() as i64 + 1
}

use std::collections::HashMap;

fn tokenize(s: &str) -> Vec<String> {
    let mut tokens = Vec::new();
    let mut current = String::new();
    for c in s.chars() {
        if c.is_alphanumeric() || c == '_' {
            current.push(c);
        } else if !current.is_empty() {
            tokens.push(std::mem::take(&mut current));
        }
    }
    if !current.is_empty() {
        tokens.push(current);
    }

    tokens
}

fn is_numeric_token(s: &str) -> bool {
    s.parse::<f64>().is_ok()
}

fn plagiarism_check(code1: &[String], code2: &[String]) -> bool {
    let c1 = code1.join(" ");
    let c2 = code2.join(" ");
    if c1 == c2 {
        return false;
    }

    let d1 = tokenize(&c1);
    let d2 = tokenize(&c2);

    let mut r_cand: HashMap<String, String> = HashMap::new();
    for (v, w) in d1.iter().zip(d2.iter()) {
        if v != w && !is_numeric_token(v) {
            r_cand.insert(v.clone(), w.clone());
        }
    }

    let renamed: Vec<String> = d1
        .iter()
        .map(|t| r_cand.get(t).cloned().unwrap_or_else(|| t.clone()))
        .collect();

    renamed == d2
}

fn shape_area(n: i64) -> i64 {
    if n > 1 {
        shape_area(n - 1) + 4 * (n - 1)
    } else {
        1
    }
}

fn stone_blocks(h: &[i64]) -> i64 {
    let mut height: Vec<i64> = Vec::new();
    let mut blocks = 0i64;

    for &i in h {
        while let Some(&last) = height.last() {
            if last > i {
                height.pop();
            } else {
                break;
            }
        }
        if let Some(&last) = height.last() {
            if last == i {
                continue;
            }
        }

        height.push(i);
        blocks += 1;
    }

    blocks
}