Challenge: Closest Seat

Lab C++ Intermediate 20 points

A cinema row has seats numbered by whole numbers. Process q commands with a std::set: add x marks seat x as taken; near x prints the taken seat closest to x (the smaller one on a tie), or none if no seat is taken.

Input

Line 1: q. Then q commands.

Output

One line per near.

Example

Input

6
near 5
add 10
add 2
near 5
near 7
near 100

Output

none
2
10
10

Sample input available Sample output available

Editor

C++

Hints

lower_bound(x) gives the first seat ≥ x.

The closest is either that seat or the one just before it (prev(it)).

Solution explanation

A balanced tree finds neighbours of x in O(log n) – something a hash set can't do.

Show solution

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    int q;
    cin >> q;
    set<long long> taken;
    while (q--) {
        string cmd;
        long long x;
        cin >> cmd >> x;
        if (cmd == "add") {
            taken.insert(x);
            continue;
        }
        if (taken.empty()) {
            cout << "none" << endl;
            continue;
        }
        auto it = taken.lower_bound(x);          // first seat >= x
        long long best;
        if (it == taken.end()) best = *prev(it);
        else if (it == taken.begin()) best = *it;
        else {
            long long above = *it, below = *prev(it);
            best = (x - below <= above - x) ? below : above;
        }
        cout << best << endl;
    }
    return 0;
}

Output

Answer