Minimum threshold for inversion pairs count

impl Solution {
  pub fn min_threshold(nums: Vec<i32>, k: i32) -> i32 {
    // Binary search on the threshold x.
    // For a given x, count inversion pairs (i<j) with nums[i]>nums[j] and nums[i]-nums[j]<=x.
    // That means: nums[j] < nums[i] <= nums[j] + x.
    // 
    // We need at least k such pairs. Binary search for minimum x.
    // For counting: use a modified merge sort or BIT.
    // 
    // For a given threshold x, sweep from left to right. For each j, count how many
    // previous i have nums[i] in range (nums[j], nums[j]+x].
    // Use a BIT indexed by value. But values up to 10^9, so coordinate compress.
    
    let n = nums.len();
    if n <= 1 { return -1; }
    
    // Coordinate compress
    let mut sorted_vals: Vec<i32> = nums.clone();
    sorted_vals.sort();
    sorted_vals.dedup();
    
    let compress = |v: i32| -> usize {
      sorted_vals.binary_search(&v).unwrap() + 1 // 1-indexed
    };
    
    let m = sorted_vals.len();
    
    // BIT (Fenwick tree)
    struct BIT {
      tree: Vec<i64>,
      n: usize,
    }
    impl BIT {
      fn new(n: usize) -> Self { BIT { tree: vec![0; n + 1], n } }
      fn update(&mut self, mut i: usize, val: i64) {
        while i <= self.n { self.tree[i] += val; i += i & i.wrapping_neg(); }
      }
      fn query(&self, mut i: usize) -> i64 {
        let mut s = 0i64;
        while i > 0 { s += self.tree[i]; i -= i & i.wrapping_neg(); }
        s
      }
      fn range_query(&self, l: usize, r: usize) -> i64 {
        if l > r { return 0; }
        self.query(r) - if l > 0 { self.query(l - 1) } else { 0 }
      }
    }
    
    let count_pairs = |threshold: i64| -> i64 {
      let mut bit = BIT::new(m);
      let mut cnt = 0i64;
      for j in 0..n {
        // Count previous elements in range (nums[j], nums[j] + threshold]
        let lo = nums[j] as i64 + 1;
        let hi = nums[j] as i64 + threshold;
        // Find compressed indices for lo and hi
        let l_idx = sorted_vals.partition_point(|&v| (v as i64) < lo) + 1; // 1-indexed
        let r_idx = sorted_vals.partition_point(|&v| (v as i64) <= hi); // 1-indexed (inclusive)
        if l_idx <= r_idx && r_idx >= 1 {
          cnt += bit.range_query(l_idx, r_idx);
        }
        let ci = compress(nums[j]);
        bit.update(ci, 1);
      }
      cnt
    };
    
    // Binary search on threshold
    // threshold range: 0 to max_diff
    // At threshold = 0: count pairs where nums[i] > nums[j] and nums[i]-nums[j] <= 0 -> 0 pairs
    // We need the minimum threshold where count >= k
    
    // Max possible threshold: max(nums) - min(nums)
    let max_val = *nums.iter().max().unwrap() as i64;
    let min_val = *nums.iter().min().unwrap() as i64;
    let max_threshold = max_val - min_val;
    
    // First check if even with max threshold we can get k pairs
    // Max threshold = all inversion pairs
    let total_inversions = count_pairs(max_threshold);
    if total_inversions < k as i64 {
      return -1;
    }
    
    let mut lo = 0i64;
    let mut hi = max_threshold;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if count_pairs(mid) >= k as i64 {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    
    lo as i32
  }
}