Seat Reservation Manager

Implement SeatManager to manage seats numbered from 1 through n.

• SeatManager(n) creates a manager with all seats available.
• reserve() reserves the available seat with the smallest number and returns that number.
• unreserve(seatNumber) makes a reserved seat available again.

Every call to reserve has at least one available seat. Every call to unreserve refers to a seat that is currently reserved.

Example 1:

Input: ["SeatManager","reserve","reserve","unreserve","reserve"]
[[3],[],[],[1],[]]

Output: [null,1,2,null,1]

Explanation: The first two calls reserve seats 1 and 2. Releasing seat 1 makes it the smallest available seat again, so the final reserve returns 1.

Example 2:

Input: ["SeatManager","reserve","unreserve","reserve"]
[[1],[],[1],[]]

Output: [null,1,null,1]

Explanation: There is only one seat. After reserving and releasing it, the next reserve returns seat 1 again.

Example 3:

Input: ["SeatManager","reserve","reserve","reserve","unreserve","unreserve","reserve","reserve"]
[[4],[],[],[],[3],[1],[],[]]

Output: [null,1,2,3,null,null,1,3]

Explanation: The first three reservations return 1, 2, and 3. Seats 3 and 1 are then released. The next two reservations return 1 and 3 in that order, ahead of the never-reserved seat 4.

Constraints:

• 1 <= n <= 100000
• 1 <= seatNumber <= n
• At most 100000 calls are made to reserve and unreserve combined.
• A seat is available whenever reserve is called.
• A seat is reserved whenever unreserve is called for it.