§ lower_bound binary search with closed intervals

// find rightmost ix such that ps[ix].b < t
ll max_earlier(ll t, vector<P> &ps) {
  assert(ps.size() > 0);
  // [l, r]
  ll l = 0, r = ps.size()-1;
  // closed interval.
  int ans = -1;
  while (l <= r) {
    ll mid = l + (r-l)/2;
    if (ps[mid].b < t) {
      // we have considered `mid`.
      // now move to the higher range to find other candidates.
      ans = max(ans, mid);
      l = mid+1;
    } else {
     // ps[mid] does not satisfy our invariant.
     // move to the lower range.
     r = mid-1;
    }
  }
  assert(ps[l].b < t);
  if (l + 1 < ps.size()) { assert(ps[l+1].b >= t); }
  return ans;
}