class SegmentTree {
    // Сегментне дерево для пошуку максимума
public:
    SegmentTree(const unsigned int arr_size_, const std::vector<int>& array_)
        : arr_size(arr_size_)
        , array(array_)
        , tree_size(arr_size_ << 1U) // розмір вектора для сегментного дерева 2 * розмір 
                                     // оригінального вектора
    {
        seg_tree.resize(tree_size, 0);
        // Заповнення листків сегментного дерева елементами з оригінального вектора
        for (unsigned int i = (tree_size >> 1U), j = 0;
             i < tree_size && j < arr_size; ++i, ++j) {
            seg_tree[i] = array[j];
        }
        // Заповнення решти сегментного дерева за певною характеристикою:
        // сумою, мінімумом, максимумом і т.д.
        // Елемент у позиції 0 ігнорується
        for (unsigned int i = (tree_size >> 1U) - 1; i >= 1; --i) {
            seg_tree[i]
                = std::ranges::max(seg_tree[i << 1U], seg_tree[(i << 1U) + 1]);
        }
    }

    void update_tree(const int value, unsigned int pos)
    {
        // Додавання нового числового елемента до сегментного дерева та
        // перезбирання його наново з урахуванням змін
        pos += arr_size; // Перенесення позиції до листків дерева задля
                         // перезбирання знизу вгору
        seg_tree[pos] = value;

        while (pos > 1) {
            pos >>= 1U;
            seg_tree[pos] = std::ranges::max(seg_tree[pos << 1U],
                                             seg_tree[(pos << 1U) + 1]);
        }
    }

    auto find_max(unsigned int left, unsigned int right)
    {
        // Знаходження максимуму, працює лише для сегментних дерев побудованих
        // для пошуку максимуму
        left += arr_size; // Перенесення позицій до індексів листків дерева для
        right += arr_size; // пошуку знизу вгору

        int max_value { std::numeric_limits<int>::min() };
        while (left <= right) {
            // Властивість індексу лівої гілки — завжди парний
            if ((left & 1U) == 1) {
                max_value = std::ranges::max(max_value, seg_tree[left++]);
            }

            // Властивість індексу правої гілки — завжди непарний
            if ((right & 1U) == 0) {
                max_value = std::ranges::max(max_value, seg_tree[right--]);
            }

            left >>= 1U; // Ділення на 2, тобто перехід на вищий рівень дерева
            right >>= 1U;
        }
        return max_value;
    }

private:
    unsigned int arr_size;
    std::vector<int> array;
    unsigned int tree_size;
    std::vector<int> seg_tree;
};

class Solution {
public:
    auto numOfUnplacedFruits(const std::vector<int>& fruits,
                             const std::vector<int>& baskets) -> int
    {
        int answer { 0 };
        auto baskets_size
            = static_cast<unsigned int>(std::ranges::size(baskets));
        SegmentTree SegTree(baskets_size, baskets);
        for (const auto& fruit : fruits) {
            if (SegTree.find_max(0, baskets_size - 1) < fruit) {
                ++answer;
            } else {
                unsigned int low { 0 };
                unsigned int high { baskets_size - 1 };
                while (low < high) {
                    // low + (high - low)/2
                    unsigned int mid = (low & high) + ((low ^ high) >> 1U);
                    if (SegTree.find_max(low, mid) < fruit) {
                        low = mid + 1;
                    } else {
                        high = mid;
                    }
                }
                SegTree.update_tree(0, low);
            }
        }
        return answer;
    }
};