#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

class UberShuttle {
private:
    struct Interval {
        int l, r;

        Interval(int left, int right) : l(left), r(right) {}
    };

    int n;

    // l -> r
    unordered_map<int, int> startMap;

    // r -> l
    unordered_map<int, int> endMap;

    int getSeat(const Interval& interval) {
        int l = interval.l;
        int r = interval.r;

        if (l == -1)
            return 0;

        if (r == n)
            return n - 1;

        return l + (r - l) / 2;
    }

    int getDistance(const Interval& interval) {
        int l = interval.l;
        int r = interval.r;

        if (l == -1)
            return r;

        if (r == n)
            return n - 1 - l;

        return (r - l) / 2;
    }

    struct Compare {
        UberShuttle* shuttle;

        Compare(UberShuttle* s = nullptr) {
            shuttle = s;
        }

        bool operator()(const Interval& a,
                        const Interval& b) const {

            int distA = shuttle->getDistance(a);
            int distB = shuttle->getDistance(b);

            if (distA == distB) {
                return shuttle->getSeat(a) >
                       shuttle->getSeat(b);
            }

            return distA < distB;
        }
    };

    priority_queue<
        Interval,
        vector<Interval>,
        Compare
    > pq;

public:
    UberShuttle(int seats)
        : n(seats), pq(Compare(this)) {

        pq.push(Interval(-1, n));

        startMap[-1] = n;
        endMap[n] = -1;
    }

    int board() {

        while (!pq.empty()) {

            Interval curr = pq.top();
            pq.pop();

            // Ignore stale intervals
            if (!startMap.count(curr.l) ||
                startMap[curr.l] != curr.r) {
                continue;
            }

            int seat = getSeat(curr);

            startMap.erase(curr.l);
            endMap.erase(curr.r);

            Interval left(curr.l, seat);
            Interval right(seat, curr.r);

            pq.push(left);
            pq.push(right);

            startMap[left.l] = left.r;
            endMap[left.r] = left.l;

            startMap[right.l] = right.r;
            endMap[right.r] = right.l;

            return seat;
        }

        return -1;
    }

    void dropOff(int p) {

        int left = endMap[p];
        int right = startMap[p];

        startMap.erase(p);
        endMap.erase(p);

        Interval merged(left, right);

        startMap[left] = right;
        endMap[right] = left;

        pq.push(merged);
    }
};

int main() {

    UberShuttle shuttle(10);

    cout << shuttle.board() << endl; // 0
    cout << shuttle.board() << endl; // 9
    cout << shuttle.board() << endl; // 4
    cout << shuttle.board() << endl; // 2

    shuttle.dropOff(4);

    cout << shuttle.board() << endl; // 5

    return 0;
}