1670.cpp

class FrontMiddleBackQueue {
  public:
    deque<int> left, right;

    void balance() {
        if (size(left) > size(right)) {
            right.push_front(left.back());
            left.pop_back();
        }

        if (size(left) + 1 < size(right)) {
            left.push_back(right.front());
            right.pop_front();
        }
    }

    void pushFront(int val) {
        left.push_front(val);
        balance();
    }

    void pushMiddle(int val) {
        left.push_back(val);
        balance();
    }

    void pushBack(int val) {
        right.push_back(val);
        balance();
    }

    int popFront() {
        if (size(left) == 0) {
            if (size(right) == 0) return -1;
            const int res = right.front();
            right.pop_front();
            return res;
        }
        const int res = left.front();
        left.pop_front();
        balance();
        return res;
    }

    int popMiddle() {
        if (size(right) + size(left) == 0) return -1;
        if (size(left) < size(right)) {
            const int res = right.front();
            right.pop_front();
            return res;
        } else {
            const int res = left.back();
            left.pop_back();
            balance();
            return res;
        }
    }

    int popBack() {
        if (size(right) == 0) {
            if (size(left) == 0) return -1;
            const int res = left.back();
            left.pop_back();
            return res;
        }
        const int res = right.back();
        right.pop_back();
        balance();
        return res;
    }
};