int bs_find_idx(const vector<int>& nums, int b, int e, int pos_eq, bool is_ub) {
  int res = pos_eq;
  int target = nums[pos_eq];
  while (b <= e) {
    int mid = b + (e - b) / 2;
    int x = nums[mid];
    if (x > target) {
      e = mid - 1;
    } else if (x < target) {
      b = mid + 1;
    } else {
      if (is_ub) {
        b = mid + 1;
        res = max(res, mid);
      } else {
        e = mid - 1;
        res = min(res, mid);
      }
    }
  }
  return res;
}

int find_lb(const vector<int>& nums, int mid) {
  // int min = mid;
  // int x = nums[mid];
  // for (int i = mid; i >= 0; i--) {
  //   if (nums[i] != x) {
  //     break;
  //   }
  //   min = i;
  // }
  // return min;
  return bs_find_idx(nums, 0, mid, mid, /*is_ub=*/false);
}

int find_ub(const vector<int>& nums, int mid) {
  // int max = mid;
  // int x = nums[mid];
  // for (int i = mid; i < nums.size(); i++) {
  //   if (nums[i] != x) {
  //     break;
  //   }
  //   max = i;
  // }
  // return max;
  return bs_find_idx(nums, mid, nums.size() - 1, mid, /*is_ub=*/true);
}

class Solution {
public:
  vector<int> searchRange(const vector<int>& nums, int target) {
    // [b, e]
    int b = 0;
    int e = nums.size() - 1;
    while (b <= e) {
      int mid = b + (e - b) / 2;
      int x = nums[mid];
      if (x < target) {
        b = mid + 1;
      } else if (x > target) {
        e = mid - 1;
      } else {
        int min = find_lb(nums, mid);
        int max = find_ub(nums, mid);
        return {min, max};
      }
    }
    return {-1, -1};
  }
};