/*  You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.

    From left to right, place the fruits according to these rules:

        1.Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
        2.Each basket can hold only one type of fruit.
        3.If a fruit type cannot be placed in any basket, it remains unplaced.

    Return the number of fruit types that remain unplaced after all possible allocations are made.
*/
class SegmentTree {
private:
	vector<int> segVal;
	void maintain(int node) {
		segVal[node] = max(segVal[node * 2], segVal[node * 2 + 1]);
	}
	void build(const vector<int>& vec, int node, int left, int right) {
		if (left == right) {
			segVal[node] = vec[left];
			return;
		}
		int mid = (left + right) / 2;
		build(vec, node * 2, left, mid);
		build(vec, node * 2 + 1, mid + 1, right);
		maintain(node);
	}
public:
	SegmentTree(const vector<int>& vec) {
		size_t n = vec.size();
		segVal.resize(2 << std::bit_width(n - 1));
		build(vec, 1, 0, n - 1);
	}
	int findFirstAndUpdate(int node, int left, int right, int val) {
		if (segVal[node] < val) {
			return -1;	// not found;
		}
		if (left == right) {
			segVal[node] = -1;	// update state
			return left;
		}
		int mid = (left + right) / 2;
		int idx = findFirstAndUpdate(node * 2, left, mid, val);
		if (idx < 0) {
			idx = findFirstAndUpdate(node * 2 + 1, mid + 1, right, val);
		}
		maintain(node);
		return idx;
	}
};

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        SegmentTree t(baskets);
        int n = baskets.size(), ans = 0;
        for (int x : fruits) {
            if (t.findFirstAndUpdate(1, 0, n - 1, x) < 0) {
                ans++;
            }
        }
        return ans;
    }
};