class Solution {
 private:
 void recursive(std::vector<int> &nums, int left, int right) {
 if (left >= right) {
 return;
 }

 int mid = left + (right - left) / 2;
 int val = nums[mid];
 std::swap(nums[mid], nums[right]);
 int low = left;
 int high = right - 1;
 while (low <= high) {
 if (nums[low] > val) {
 std::swap(nums[low], nums[high--]);
 } else {
 ++low;
 }
 }
 std::swap(nums[low], nums[right]);

 recursive(nums, left, low - 1);
 recursive(nums, low + 1, right);
 }

 public:
 void quickSort(std::vector<int> &nums) {
 recursive(nums, 0, nums.size() - 1);
 }
};

size_t lowerBound(const std::vector<int> &nums, int target) {
 size_t left = 0;
 size_t right = nums.size();
 while (left < right) {
 const size_t mid = left + (right - left) / 2;
 // Find the first element >= the target
 if (nums[mid] >= target) {
 right = mid;
 } else {
 left = mid + 1;
 }
 }
 return left;
}

class PriorityQueue {
 private:
 std::vector<int> data_;

 void siftDown(size_t idx) {
 while (idx < data_.size()) {
 size_t child = 2 * idx + 1;
 if (child >= data_.size()) {
 break;
 }
 if (child + 1 < data_.size() && data_[child] < data_[child + 1]) {
 child += 1;
 }
 if (data_[child] < data_[idx]) {
 break;
 }
 std::swap(data_[idx], data_[child]);
 idx = child;
 }
 }

 public:
 explicit PriorityQueue(size_t capacity) {
 data_.reserve(capacity);
 }
 explicit PriorityQueue(const std::vector<int> &vec) {
 data_ = vec;
 for (size_t i = data_.size() / 2 - 1; i != -1; --i) {
 siftDown(i);
 }
 }

 void push(int val) {
 data_.push_back(val);

 size_t idx = data_.size() - 1;
 size_t parent = (idx - 1) / 2;
 while (idx > 0 && data_[parent] < data_[idx]) {
 std::swap(data_[parent], data_[idx]);
 idx = parent;
 parent = (idx - 1) / 2;
 }
 }

 int pop() {
 std::swap(data_.front(), data_.back());
 int val = data_.back();
 data_.pop_back();

 size_t idx = 0;
 while (idx < data_.size()) {
 size_t child = 2 * idx + 1;
 if (child >= data_.size()) {
 break;
 }
 if (child + 1 < data_.size() && data_[child] < data_[child + 1]) {
 child += 1;
 }
 if (data_[child] < data_[idx]) {
 break;
 }
 std::swap(data_[idx], data_[child]);
 idx = child;
 }

 return val;
 }
};