#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 2; unordered_map<ll, ll> l, r; ll n, vt[N]; int q, id; struct Data { ll z, x, y; }; struct cmp { bool operator()(Data u, Data v) { return (u.z < v.z || (u.z == v.z && u.x > v.x)); } }; priority_queue<Data, vector<Data>, cmp> pq; void PUSH(ll x, ll y) { r[x] = y; l[y] = x; ll t, z; if (x == 0) z = y - 2; else if (y == n + 1) z = n - x - 1; else { t = (x + y) / 2; z = min(t - x - 1, y - t - 1); } pq.push({ z, x, y }); } main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("atm.inp","r",stdin); cin >> n >> q; pq.push({ n, 0, n + 1 }); for (int i = 1; i <= q; i++) { int x; cin >> x; if (x == 1) { Data u = pq.top(); while (pq.size() > 1 && (r[u.x] != u.y || l[u.y] != u.x)) { pq.pop(); u = pq.top(); } id++; if (u.x == 0) { vt[id] = 1; PUSH(1, u.y); } else if (u.y == n + 1) { vt[id] = n; PUSH(u.x, n); } else { vt[id] = (u.x + u.y) / 2; ll t = vt[id]; PUSH(u.x, t); PUSH(t, u.y); } cout << vt[id] << '\n'; } else { int y; cin >> y; ll t = vt[y]; if (t == 1) PUSH(0, r[t]); else if (t == n) PUSH(l[t], n + 1); else PUSH(l[t], r[t]); } } }