array/

lib.rs

//! # Array

#![feature(test)]

extern crate test;

/// 73m Set Matrix Zeroes
struct Sol73 {}

impl Sol73 {
    /// -2^31 <= M_ij <= 2^31-1
    /// 1 <= M, N <= 200
    pub fn set_zeroes(matrix: &mut [Vec<i32>]) {
        let (rows, cols) = (matrix.len(), matrix[0].len());

        let zero_row0 = matrix[0].contains(&0);
        let zero_col0 = matrix.iter().any(|row| row[0] == 0);

        for r in 1..rows {
            for c in 1..cols {
                if matrix[r][c] == 0 {
                    (matrix[0][c], matrix[r][0]) = (0, 0);
                }
            }
        }

        for r in 1..rows {
            for c in 1..cols {
                if matrix[0][c] == 0 || matrix[r][0] == 0 {
                    matrix[r][c] = 0;
                }
            }
        }

        if zero_col0 {
            for row in matrix.iter_mut() {
                row[0] = 0;
            }
        }
        if zero_row0 {
            for v in matrix[0].iter_mut() {
                *v = 0;
            }
        }
    }
}

/// 747 Largest Number At Least Twice of Others
struct Sol747 {}

impl Sol747 {
    /// 0 <= N_i <= 100
    pub fn dominant_index(nums: Vec<i32>) -> i32 {
        let xv = nums.iter().max().unwrap_or(&-1);

        if nums.iter().filter(|&n| n != xv).all(|n| 2 * n <= *xv) {
            return nums.iter().position(|n| n == xv).unwrap() as i32;
        }

        -1
    }
}

/// 766 Toeplitz Matrix
struct Sol766 {}

impl Sol766 {
    pub fn is_toeplitz_matrix(matrix: Vec<Vec<i32>>) -> bool {
        matrix
            .iter()
            .zip(matrix.iter().skip(1))
            .all(|(tr, br)| tr.iter().zip(br.iter().skip(1)).all(|(lv, rv)| lv == rv))
    }
}

/// 798h Smallest Rotation with Highest Score
struct Sol798 {}

impl Sol798 {
    /// 1 <= L <= 10^5
    /// 0 <= N_i < L
    pub fn best_rotation(nums: Vec<i32>) -> i32 {
        let n = nums.len();

        let mut scores = vec![0; n];
        for (i, &p) in nums.iter().enumerate() {
            let (left, right) = ((n + i - p as usize + 1) % n, (i + 1) % n);
            scores[left] -= 1;
            scores[right] += 1;
            if left > right {
                scores[0] -= 1;
            }
        }

        let (mut cur, mut best) = (0, -(n as i32));
        scores.into_iter().enumerate().fold(0, |x, (i, score)| {
            cur += score;
            if cur > best {
                best = cur;
                i
            } else {
                x
            }
        }) as _
    }
}

/// 1184 Distance Between Bus Stops
struct Sol1184;

impl Sol1184 {
    pub fn distance_between_bus_stops(distance: Vec<i32>, start: i32, destination: i32) -> i32 {
        let (mut src, mut dst) = (start as usize, destination as usize);
        if src > dst {
            (src, dst) = (dst, src);
        }

        distance[src..dst]
            .iter()
            .sum::<i32>()
            .min(distance[dst..].iter().chain(distance[..src].iter()).sum())
    }
}

/// 1394 Find Lucky Integer in an Array
struct Sol1394;

impl Sol1394 {
    /// 1 <= N, N_i <= 500
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let mut freqs = [0; 500 + 1];
        for n in arr {
            freqs[n as usize] += 1;
        }

        freqs
            .iter()
            .enumerate()
            .rev()
            .filter(|(_, f)| **f > 0)
            .find(|(n, f)| *f == n)
            .map(|(n, _)| n as i32)
            .unwrap_or(-1)
    }
}

/// 1450 Number of Students Doing Homework at a Given Time
struct Sol1450 {}
impl Sol1450 {
    pub fn busy_student(start_time: Vec<i32>, end_time: Vec<i32>, query_time: i32) -> i32 {
        start_time
            .iter()
            .zip(end_time.iter())
            .fold(0, |count, (s, e)| {
                if *s <= query_time && query_time <= *e {
                    count + 1
                } else {
                    count
                }
            })
    }
}

/// 1534 Count Good Triplets
struct Sol1534;

impl Sol1534 {
    /// O(N^3)
    pub fn count_good_triplets(arr: Vec<i32>, a: i32, b: i32, c: i32) -> i32 {
        let mut count = 0;
        for (i, x) in arr.iter().enumerate() {
            for (j, y) in arr.iter().enumerate().skip(i + 1) {
                if (x - y).abs() <= a {
                    for z in arr.iter().skip(j + 1) {
                        if (y - z).abs() <= b && (z - x).abs() <= c {
                            count += 1;
                        }
                    }
                }
            }
        }

        count
    }
}

/// 1550 Three Consecutive Odds
struct Sol1550;

impl Sol1550 {
    pub fn three_consecutive_odds(arr: Vec<i32>) -> bool {
        arr.windows(3)
            .inspect(|v| println!("-> {:?}", v))
            .any(|v| v[0] & v[1] & v[2] & 1 == 1)
    }
}

/// 1752 Check If Array Is Sorted and Rotated
struct Sol1752;

impl Sol1752 {
    pub fn check(nums: Vec<i32>) -> bool {
        println!(" * {:?}", nums);
        println!(
            ":: {}",
            nums.windows(2).fold(
                if nums[0] < nums[nums.len() - 1] { 1 } else { 0 },
                |r, v| if v[1] < v[0] { r + 1 } else { r }
            ) <= 1
        );

        let mut nums = nums;
        let Some(pinv) = nums.windows(2).position(|v| v[1] < v[0]) else {
            return true;
        };

        nums.rotate_left(pinv + 1);
        nums.windows(2).all(|v| v[0] <= v[1])
    }
}

/// 1796 Second Largest Digit in a String
struct Sol1796 {}

impl Sol1796 {
    pub fn second_highest(s: String) -> i32 {
        s.chars()
            .fold((-1, -1), |(x, x2), chr| match chr {
                '0'..='9' => {
                    let d = ('0'..='9').position(|x| x == chr).unwrap() as i32;
                    if d == x {
                        (x, x2)
                    } else if x < d {
                        (d, x)
                    } else if x2 < d {
                        (x, d)
                    } else {
                        (x, x2)
                    }
                }
                _ => (x, x2),
            })
            .1
    }
}

/// 1800 Maximum Possible Ascending Subarray Sum
struct Sol1800;

impl Sol1800 {
    pub fn max_ascending_sum(nums: Vec<i32>) -> i32 {
        nums.windows(2)
            .fold((nums[0], nums[0]), |mut kadan, v| {
                if v[1] > v[0] {
                    kadan.0 += v[1];
                } else {
                    kadan.0 = v[1];
                }
                kadan.1 = kadan.1.max(kadan.0);

                kadan
            })
            .1
    }
}

/// 1920 Build Array from Permutation
struct Sol1920;

impl Sol1920 {
    /// 1 <= N <= 1000, 0 <= N_i < N
    pub fn build_array(nums: Vec<i32>) -> Vec<i32> {
        println!("** {:?}", nums);

        fn in_place(nums: Vec<i32>) -> Vec<i32> {
            let mut nums = nums;
            for i in 0..nums.len() {
                nums[i] += 1000 * (nums[nums[i] as usize] % 1000);
            }
            for n in nums.iter_mut() {
                *n /= 1000;
            }

            nums
        }
        println!(":: {:?}", in_place(nums.to_vec()));

        nums.iter().fold(vec![], |mut v, &n| {
            v.push(nums[n as usize]);
            v
        })
    }
}

/// 2016 Maximum Difference Between Increasing Elements
struct Sol2016 {}

impl Sol2016 {
    pub fn maximum_difference(nums: Vec<i32>) -> i32 {
        let mut vmin = nums[0];
        let mut xdiff = -1;

        for n in nums.into_iter().skip(1) {
            if n > vmin {
                xdiff = xdiff.max(n - vmin);
            }
            vmin = vmin.min(n);
        }

        xdiff
    }
}

/// 2017m Grid Game
struct Sol2017;

impl Sol2017 {
    pub fn grid_game(grid: Vec<Vec<i32>>) -> i64 {
        let mut top = grid[0].iter().map(|&n| n as i64).sum::<i64>();
        let mut bottom = 0;

        (0..grid[0].len()).fold(i64::MAX, |mx, i| {
            top -= grid[0][i] as i64;
            bottom += grid[1][i] as i64;
            mx.min(top.max(bottom - grid[1][i] as i64))
        })
    }
}

/// 2033m Minimum Operations to Make a Uni-Value Grid
struct Sol2033;

impl Sol2033 {
    pub fn min_operations(grid: Vec<Vec<i32>>, x: i32) -> i32 {
        let mut nums = vec![];
        for r in 0..grid.len() {
            for c in 0..grid[0].len() {
                nums.push(grid[r][c]);
            }
        }

        nums.sort_unstable();
        let median = nums[nums.len() / 2];

        println!("-> {:?}", (&nums, median));

        let r = median % x;
        let mut ops = 0;
        for n in nums {
            if n % x != r {
                return -1;
            }
            ops += (n - median).abs() / x;
        }

        ops
    }
}

/// 2094 Finding 3-Digit Even Numbers
struct Sol2094;

impl Sol2094 {
    pub fn find_even_numbers(digits: Vec<i32>) -> Vec<i32> {
        let mut freq = [0; 10];
        digits.iter().for_each(|&d| freq[d as usize] += 1);

        println!("-> {:?}", freq);

        let mut evens = vec![];
        for h in 1..=9 {
            if freq[h] == 0 {
                continue;
            }
            freq[h] -= 1;
            for t in 0..=9 {
                if freq[t] == 0 {
                    continue;
                }
                freq[t] -= 1;
                for o in (0..=8).step_by(2) {
                    if freq[o] > 0 {
                        evens.push((100 * h + 10 * t + o) as i32);
                    }
                }
                freq[t] += 1;
            }
            freq[h] += 1;
        }

        evens
    }
}

/// 2099 Find Subsequence of Length K With the Largest Sum
struct Sol2099 {}

impl Sol2099 {
    pub fn max_subsequence(nums: Vec<i32>, k: i32) -> Vec<i32> {
        use std::cmp::Reverse;

        let mut sorted: Vec<_> = nums.iter().enumerate().collect();
        sorted.sort_by_key(|(_, n)| Reverse(*n));
        println!("-> {sorted:?}");

        sorted[0..k as usize].sort();
        println!("-> {sorted:?}");

        sorted[0..k as usize].iter().map(|(_, n)| **n).collect()
    }
}

/// 2145m Count the Hidden Sequences
struct Sol2145;

impl Sol2145 {
    /// 1 <= N <= 10^5, -10^5 <= N_i <= 10^5
    pub fn number_of_arrays(differences: Vec<i32>, lower: i32, upper: i32) -> i32 {
        let (mut x, mut n) = (0, 0);
        let mut v = 0;
        for diff in differences {
            v += diff;
            x = x.max(v);
            n = n.min(v);

            if x - n > upper - lower {
                return 0;
            }
        }

        upper - lower - (x - n) + 1
    }
}

/// 2176 Count Equal and Divisible Pairs in an Array
struct Sol2176;

impl Sol2176 {
    pub fn count_pairs(nums: Vec<i32>, k: i32) -> i32 {
        let mut count = 0;
        for (i, &x) in nums.iter().enumerate().take(nums.len() - 1) {
            for (j, &y) in nums.iter().enumerate().skip(i + 1) {
                if x == y && (i * j).is_multiple_of(k as usize) {
                    count += 1;
                }
            }
        }

        count
    }
}

/// 2190 Most Frequent Number Following Key In an Array
struct Sol2190 {}

impl Sol2190 {
    pub fn most_frequent(nums: Vec<i32>, key: i32) -> i32 {
        use std::collections::HashMap;

        let mut freqs = HashMap::new();
        for w in nums.windows(2) {
            if w[0] == key {
                freqs.entry(w[1]).and_modify(|f| *f += 1).or_insert(1);
            }
        }

        println!(
            ":? {}",
            freqs.iter().max_by_key(|&(_, f)| f).map_or(0, |(&n, _)| n)
        );

        let xfreq = freqs.values().max().unwrap();
        *freqs.iter().find(|(_, f)| *f == xfreq).unwrap().0
    }
}

/// 2200 Find All K-Distant Indices in an Array
struct Sol2200 {}

impl Sol2200 {
    pub fn find_k_distant_indices(nums: Vec<i32>, key: i32, k: i32) -> Vec<i32> {
        let k = k as usize;
        let mut l = 0;
        nums.iter()
            .enumerate()
            .filter(|(_, n)| **n == key)
            .fold(vec![], |mut kdists, (r, _)| {
                for i in l.max(r.saturating_sub(k))..=(r + k).min(nums.len() - 1) {
                    kdists.push(i as i32);
                }
                l = r + k + 1;

                kdists
            })
    }
}

/// 2210 Count Hills and Valleys in an Array
struct Sol2210 {}

impl Sol2210 {
    pub fn count_hill_valley(mut nums: Vec<i32>) -> i32 {
        nums.dedup();
        println!("-> {nums:?}");

        nums.windows(3).fold(0, |count, w| {
            if w[0] < w[1] && w[1] > w[2] || w[0] > w[1] && w[1] < w[2] {
                count + 1
            } else {
                count
            }
        })
    }
}

/// 2248 Intersection of Multiple Array
struct Sol2248 {}

impl Sol2248 {
    pub fn intersection(nums: Vec<Vec<i32>>) -> Vec<i32> {
        use std::collections::BTreeMap;

        let mut freqs = BTreeMap::new();
        for nums in &nums {
            for n in nums {
                freqs.entry(n).and_modify(|f| *f += 1).or_insert(1);
            }
        }

        freqs
            .into_iter()
            .filter(|(_, f)| *f == nums.len())
            .map(|(&n, _)| n)
            .collect::<Vec<_>>()
    }
}

/// 2341 Maximum Number of Pairs in Array
struct Sol2341 {}

impl Sol2341 {
    pub fn number_of_pairs(mut nums: Vec<i32>) -> Vec<i32> {
        nums.sort_unstable();

        let (pairs, leftovers) = nums
            .chunk_by(PartialEq::eq)
            .fold((0, 0), |(pairs, leftovers), chunk| {
                (pairs + chunk.len() / 2, leftovers + (chunk.len() & 1))
            });

        vec![pairs as i32, leftovers as i32]
    }
}

/// 2419m Longest Subarray With Maximum Bitwise AND
struct Sol2419 {}

impl Sol2419 {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let (mut x, mut cur) = (0, 0);

        nums.iter().fold(0, |mut x_len, &n| {
            if x < n {
                x = n;
                (x_len, cur) = (0, 0);
            }

            if x == n {
                cur += 1;
            } else {
                cur = 0;
            }

            x_len.max(cur)
        })
    }
}

/// 2536m Increment Submatrices by One
struct Sol2536 {}

impl Sol2536 {
    pub fn range_add_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = n as usize;

        let diffs = queries
            .iter()
            .fold(vec![vec![0; n + 1]; n + 1], |mut diffs, query| {
                let [r1, c1, r2, c2, ..] = query[..] else {
                    panic!()
                };

                let (r1, r2, c1, c2) = (r1 as usize, r2 as usize, c1 as usize, c2 as usize);

                diffs[r1][c1] += 1;
                diffs[r2 + 1][c1] -= 1;
                diffs[r1][c2 + 1] -= 1;
                diffs[r2 + 1][c2 + 1] += 1;

                diffs
            });

        println!("-> {diffs:?}");

        let mut matrix = vec![vec![0; n as usize]; n as usize];
        for r in 0..n {
            for c in 0..n {
                let left = if r == 0 { 0 } else { matrix[r - 1][c] };
                let above = if c == 0 { 0 } else { matrix[r][c - 1] };
                let diagonal = if r == 0 || c == 0 {
                    0
                } else {
                    matrix[r - 1][c - 1]
                };

                matrix[r][c] = diffs[r][c] + left + above - diagonal;
            }
        }

        matrix
    }
}

/// 2780m Minimum Index of a Valid Split
struct Sol2780;

impl Sol2780 {
    pub fn minimum_index(nums: Vec<i32>) -> i32 {
        let mut copy = nums.to_vec();
        copy.sort_unstable();

        let (mut dominent, mut frq) = (0, 0);
        copy.iter().fold((0, 0), |(d, mut f), &n| {
            if d == n {
                f += 1;
            } else {
                f = 1;
            }

            if f > frq {
                frq = f;
                dominent = n;
            }

            (n, f)
        });

        println!("-> {:?}", (dominent, frq));

        let mut f = 0;
        for (i, &n) in nums.iter().enumerate() {
            if n == dominent {
                f += 1;
            }

            if f > i.div_ceil(2) && (frq - f) > (nums.len() - i - 1) / 2 {
                return i as i32;
            }
        }

        -1
    }

    /// Majority Voting Algorithm: Boyer-Moore
    #[expect(non_snake_case)]
    fn Boyer_Moore(nums: Vec<i32>) -> i32 {
        nums.iter()
            .fold((nums[0], 0), |(mut majority, mut frq), &n| {
                if n == majority {
                    frq += 1;
                } else {
                    frq -= 1;
                }

                if frq == 0 {
                    majority = n;
                }

                (majority, frq)
            })
            .0
    }
}

/// 2873 Maximum Value of an Ordered Triplet I
struct Sol2873;

impl Sol2873 {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let mut value = -1;
        for i in 0..nums.len() {
            for j in i + 1..nums.len() {
                for k in j + 1..nums.len() {
                    value = value.max((nums[i] - nums[j]) as i64 * nums[k] as i64);
                }
            }
        }

        value.max(0)
    }
}

/// 2874m Maximum Value of an Ordered Triplet II
struct Sol2874;

impl Sol2874 {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        let mut value = 0;
        let (mut lmax, mut diff) = (0, 0);
        for n in nums {
            value = value.max(diff as i64 * n as i64);

            diff = diff.max(lmax - n);
            lmax = lmax.max(n);
        }

        value
    }
}

/// 2894 Divisible and Non-divisible Sums Difference
struct Sol2894 {}

impl Sol2894 {
    pub fn difference_of_sums(n: i32, m: i32) -> i32 {
        2 * (1..=n).filter(|&v| v % m != 0).sum::<i32>() - n * (n + 1) / 2
    }
}

/// 2942 Find Words Containing Character
struct Sol2942 {}

impl Sol2942 {
    pub fn find_words_containing(words: Vec<String>, x: char) -> Vec<i32> {
        println!(
            ":: {:?}",
            words
                .iter()
                .enumerate()
                .filter_map(|(i, word)| if word.contains(x) {
                    Some(i as i32)
                } else {
                    None
                })
                .collect::<Vec<_>>()
        );

        words
            .iter()
            .enumerate()
            .filter(|(_, word)| word.contains(x))
            .map(|(i, _)| i as i32)
            .collect()
    }
}

/// 2946 Matrix Similarity After Cyclic Shifts
struct Sol2946 {}

impl Sol2946 {
    pub fn are_similar(mat: Vec<Vec<i32>>, k: i32) -> bool {
        let k = k as usize % mat[0].len();

        mat.iter().enumerate().all(|(r, row)| {
            row.iter()
                .enumerate()
                .all(|(c, &n)| n == mat[r][(c + k) % mat[0].len()])
        })
    }
}

/// 2966m Divide Array Into Arrays With Max Difference
struct Sol2966 {}

impl Sol2966 {
    pub fn divide_array(mut nums: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
        nums.sort_unstable();
        nums.chunks(3)
            .map(|chk| {
                if chk[2] - chk[0] > k {
                    None
                } else {
                    Some(chk.to_vec())
                }
            })
            .collect::<Option<Vec<Vec<i32>>>>()
            .unwrap_or_default()
    }
}

/// 3105 Longest Strictly Increasing or Strictly Decreasing Subarray
struct Sol3105;

impl Sol3105 {
    pub fn longest_monotonic_subarray(nums: Vec<i32>) -> i32 {
        let (mut asc, mut desc) = (0, 0);
        nums.windows(2).fold([0, 0], |mut r, v| {
            if v[0] > v[1] {
                r[0] += 1;
                desc = desc.max(r[0]);
            } else {
                r[0] = 0;
            }
            if v[1] > v[0] {
                r[1] += 1;
                asc = asc.max(r[1]);
            } else {
                r[1] = 0;
            }
            println!("{:?}", r);
            r
        });

        println!(":: {:?}", asc.max(desc) + 1);

        match (asc, desc) {
            (0, 0) => 1,
            _ => asc.max(desc) + 1,
        }
    }
}

/// 3151 Special Array I
struct Sol3151;

impl Sol3151 {
    pub fn is_array_special(nums: Vec<i32>) -> bool {
        nums.windows(2)
            .fold(true, |r, v| if (v[0] ^ v[1]) & 1 == 0 { false } else { r })
    }
}

/// 3169m Count Days Without Meetings
struct Sol3169;

impl Sol3169 {
    pub fn count_days(days: i32, meetings: Vec<Vec<i32>>) -> i32 {
        use std::collections::BTreeMap;

        let mut meetings = meetings;
        for meeting in meetings.iter_mut() {
            meeting[1] += 1;
        }

        let mut sweep = BTreeMap::new();
        for meeting in &meetings {
            sweep
                .entry(&meeting[0])
                .and_modify(|f| *f += 1)
                .or_insert(1);
            sweep
                .entry(&meeting[1])
                .and_modify(|f| *f -= 1)
                .or_insert(-1);
        }

        let days = days + 1;
        sweep.entry(&days).or_insert(0);

        println!("-> {:?}", (std::any::type_name_of_val(&sweep), &sweep));

        let (mut cur_meeting, mut cur_day) = (0, 1);
        sweep.iter().fold(0, |mut rst, (&day, &diff)| {
            if cur_meeting == 0 {
                rst += day - cur_day;
            }
            cur_meeting += diff;
            cur_day = *day;

            rst
        })
    }
}

/// 3195m Find the Minimum Area to Cover All Ones I
struct Sol3195 {}

impl Sol3195 {
    pub fn minimum_area(grid: Vec<Vec<i32>>) -> i32 {
        let (mut left, mut right) = (grid[0].len(), 0);
        let (mut top, mut bottom) = (grid.len(), 0);

        for (r, row) in grid.iter().enumerate() {
            for (c, &n) in row.iter().enumerate() {
                if n == 1 {
                    left = left.min(c);
                    right = right.max(c);

                    top = top.min(r);
                    bottom = bottom.max(r);
                }
            }
        }

        ((right - left + 1) * (bottom - top + 1)) as _
    }
}

/// 3355m Zero Array Transformation I
struct Sol3355 {}

impl Sol3355 {
    pub fn is_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> bool {
        let mut diffs = vec![0; nums.len() + 1];
        for query in queries {
            diffs[query[0] as usize] += 1;
            diffs[query[1] as usize + 1] -= 1;
        }

        let mut diffs_sum = vec![];
        let mut sum = 0;
        for diff in diffs {
            sum += diff;
            diffs_sum.push(sum);
        }

        println!("-> {diffs_sum:?}");

        nums.into_iter()
            .zip(diffs_sum)
            .all(|(num, diff_sum)| num <= diff_sum)
    }
}

/// 3392 Count Subarrays of Length Three With a Condition
struct Sol3392;

impl Sol3392 {
    pub fn count_subarrays(nums: Vec<i32>) -> i32 {
        println!(
            ":: {}",
            nums.to_vec().windows(3).fold(0, |count, v| {
                if 2 * (v[0] + v[2]) == v[1] {
                    count + 1
                } else {
                    count
                }
            })
        );

        let mut count = 0;
        for i in 2..nums.len() {
            if 2 * (nums[i - 2] + nums[i]) == nums[i - 1] {
                count += 1;
            }
        }

        count
    }
}

/// 3394m Check if Grid can be Cut into Sections
struct Sol3394;

impl Sol3394 {
    #[expect(unused_variables)]
    pub fn check_valid_cuts(n: i32, mut rectangles: Vec<Vec<i32>>) -> bool {
        let mut check = |offset| {
            rectangles.sort_unstable_by_key(|v| v[offset]);

            let mut gaps = 0;
            rectangles
                .iter()
                .skip(1)
                .fold(rectangles[0][offset + 2], |end: i32, rectangle| {
                    if end <= rectangle[offset] {
                        gaps += 1;
                    }

                    end.max(rectangle[offset + 2])
                });

            gaps >= 2
        };

        check(0) || check(1)
    }
}

/// 3423 Maximum Difference Between Adjacent Elements in a Circular Array
struct Sol3423 {}

impl Sol3423 {
    /// 2 <= N <= 100
    pub fn max_adjacent_distance(nums: Vec<i32>) -> i32 {
        println!(
            ":: {}",
            nums.iter()
                .zip(nums.iter().cycle().skip(1))
                .map(|(a, b)| (a - b).abs())
                .max()
                .unwrap()
        );

        nums.windows(2)
            .fold((nums[0] - nums[nums.len() - 1]).abs(), |r, w| {
                ((w[0] - w[1]).abs()).max(r)
            })
    }
}

/// 3495m Minimum Operations to Make Array Elements Zero
struct Sol3495 {}

impl Sol3495 {
    /// 1 <= Q <= 10^5
    /// 1 <= Q_0, Q_1 <= 10^9
    pub fn min_operations(queries: Vec<Vec<i32>>) -> i64 {
        // [1, n]
        let ops = |n| {
            let mut i = 1;
            let mut base = 1;

            let mut ops = 0;
            while base <= n {
                ops += ((i + 1) >> 1) * (((base << 1) - 1).min(n) - base + 1);
                i += 1;
                base <<= 1;
            }

            ops
        };

        println!(
            ":? {}",
            queries
                .iter()
                .map(|qry| (qry[0] as i64, qry[1] as i64))
                .map(|(l, r)| (1..31)
                    .scan(1i64, |prv, power| {
                        let start = l.max(*prv);
                        let end = r.min(4 * *prv - 1);
                        *prv *= 4;

                        let ops = if end >= start {
                            (end - start + 1) * power
                        } else {
                            0
                        };

                        Some(ops)
                    })
                    .sum::<i64>())
                .map(|ops| (ops + 1) / 2)
                .sum::<i64>()
        );

        queries
            .iter()
            .map(|v| (v[0] as i64, v[1] as i64))
            .fold(0, |m_ops, (l, r)| m_ops + (1 + ops(r) - ops(l - 1)) / 2)
    }
}

#[cfg(test)]
mod tests;