Minimize the maximum adjacent element difference

impl Solution {
  pub fn min_difference(nums: Vec<i32>) -> i32 {
    let n = nums.len();

    if nums.iter().all(|&x| x != -1) {
      return (0..n-1).map(|i| (nums[i] - nums[i+1]).abs()).max().unwrap_or(0);
    }
    if nums.iter().all(|&x| x == -1) { return 0; }

    let fixed_max = (0..n-1)
      .filter(|&i| nums[i] != -1 && nums[i+1] != -1)
      .map(|i| (nums[i] - nums[i+1]).abs() as i64)
      .max()
      .unwrap_or(0);

    // check(mid): can we pick x, y such that after replacing all -1s with x or y,
    // every adjacent pair differs by <= mid?
    //
    // For each contiguous run of -1s:
    //   a = left neighbor (if exists), b = right neighbor (if exists)
    //   Ia = [a-mid, a+mid] (constraint for first -1 in run from left)
    //   Ib = [b-mid, b+mid] (constraint for last -1 in run from right)
    //
    //   Length 1: value must satisfy BOTH a and b constraints → intersect Ia ∩ Ib.
    //     Add intersection as single interval (empty = infeasible immediately).
    //
    //   Length >= 2:
    //     If we assign all -1s in this run the SAME value v, we need v ∈ Ia ∩ Ib.
    //       → if Ia ∩ Ib non-empty, add the intersection as a single interval.
    //     If we split (some x, some y), adjacent -1s with different values must have |x-y|<=mid.
    //       First -1 can be set to x/y in Ia, last -1 can be set to x/y in Ib.
    //       → add both Ia and Ib as independent intervals (the greedy |y-x|<=mid constraint handles this).
    //
    //     We try BOTH options and add the minimal set of intervals.
    //     In practice: add intersection (if non-empty) as a single interval,
    //     and ALSO add both Ia and Ib (for the split option).
    //     The greedy will pick whichever option requires fewer constraints.
    //
    //     Simpler: for runs >= 2, always add ONLY the intersection (if non-empty) as a single interval.
    //     If intersection is empty, add Ia and Ib as two intervals.
    //     Reason: if intersection is non-empty, we can use the SAME value for all -1s in the run,
    //     which is strictly better than splitting (avoids the |x-y|<=mid constraint on x,y).
    //     If intersection is empty, we must split (x and y must cover Ia and Ib respectively
    //     with |x-y|<=mid enforced by the greedy).
    //
    //   Edge cases:
    //     Run at start (no a): only Ib matters → add Ib as single interval (or unconstrained).
    //     Run at end (no b): only Ia matters → add Ia as single interval.
    //     Run at both ends (no a, no b): no constraint.

    // check_once: for multi-runs with non-empty intersection, if `optional_as_pairs` is false
    // we treat them as singles (same value for the whole run); if true, we treat them as
    // split pairs (|x-y| <= mid enforced). Calling both and OR-ing handles the case where
    // the intersection is non-empty but the split option is actually needed.
    let check_once = |mid: i64, optional_as_pairs: bool| -> bool {
      // singles: intervals where ONE of x,y must lie inside
      // pairs: (Ia, Ib) where we need x in one and y in the other, with |x-y|<=mid
      let mut singles: Vec<(i64, i64)> = Vec::new();
      // pairs within the same run where we can't use a single value
      let mut pairs: Vec<((i64,i64),(i64,i64))> = Vec::new();

      let mut i = 0;
      while i < n {
        if nums[i] == -1 {
          let seg_start = i;
          while i < n && nums[i] == -1 { i += 1; }
          let seg_end = i - 1;
          let seg_len = seg_end - seg_start + 1;

          let a: Option<i64> = if seg_start > 0 { Some(nums[seg_start-1] as i64) } else { None };
          let b: Option<i64> = if seg_end + 1 < n { Some(nums[seg_end+1] as i64) } else { None };

          let ia = a.map(|av| (av - mid, av + mid));
          let ib = b.map(|bv| (bv - mid, bv + mid));

          if seg_len == 1 {
            // Single -1: intersection of both neighbor constraints
            let lo = ia.map_or(i64::MIN/2, |(l,_)| l).max(ib.map_or(i64::MIN/2, |(l,_)| l));
            let hi = ia.map_or(i64::MAX/2, |(_,r)| r).min(ib.map_or(i64::MAX/2, |(_,r)| r));
            if lo > hi { return false; }
            singles.push((lo, hi));
          } else {
            // Length >= 2
            match (ia, ib) {
              (Some(ia_iv), Some(ib_iv)) => {
                let int_lo = ia_iv.0.max(ib_iv.0);
                let int_hi = ia_iv.1.min(ib_iv.1);
                if int_lo <= int_hi {
                  // Intersection non-empty: same value works for entire run.
                  // But split (x in Ia, y in Ib with |x-y|<=mid) may also work
                  // and can be more flexible. Try both via optional_as_pairs flag.
                  if optional_as_pairs {
                    pairs.push((ia_iv, ib_iv));
                  } else {
                    singles.push((int_lo, int_hi));
                  }
                } else {
                  // Must use x and y for different parts; they'll be adjacent in this run
                  pairs.push((ia_iv, ib_iv));
                }
              }
              (Some(ia_iv), None) => singles.push(ia_iv),
              (None, Some(ib_iv)) => singles.push(ib_iv),
              (None, None) => {}
            }
          }
        } else {
          i += 1;
        }
      }

      // Now check if we can find x, y satisfying all singles and all pairs.
      // singles: each must be covered by x or y.
      // pairs: (Pa, Pb) → (x in Pa and y in Pb) or (x in Pb and y in Pa), with |x-y|<=mid.
      //
      // Greedy: sort all intervals by right endpoint. Pick x = right end of first interval.
      // For uncovered intervals, they must be covered by y. If has_pairs, enforce |y-x|<=mid.
      let has_pairs = !pairs.is_empty();
      let mut ivs = singles.clone();
      for (pa, pb) in &pairs {
        ivs.push(*pa);
        ivs.push(*pb);
      }

      if ivs.is_empty() { return true; }

      ivs.sort_unstable_by_key(|&(_, r)| r);

      let x = ivs[0].1;
      let mut y_lo = if has_pairs { x - mid } else { i64::MIN / 2 };
      let mut y_hi = if has_pairs { x + mid } else { i64::MAX / 2 };

      for &(l, r) in &ivs {
        if x >= l && x <= r { continue; }
        y_lo = y_lo.max(l);
        y_hi = y_hi.min(r);
        if y_lo > y_hi { return false; }
      }
      true
    };

    let check = |mid: i64| -> bool {
      // Try same-value option for multi-runs with non-empty intersection, and also
      // the split option; feasible if either approach works.
      check_once(mid, false) || check_once(mid, true)
    };

    let max_val = nums.iter().filter(|&&x| x != -1).max().cloned().unwrap_or(0) as i64;
    let mut lo = fixed_max;
    let mut hi = max_val + 1;

    while lo < hi {
      let mid = (lo + hi) / 2;
      if check(mid) { hi = mid; } else { lo = mid + 1; }
    }
    lo as i32
  }
}