#include <bits/stdc++.h>   using namespace std;   #pragma comment(linker,  /STACK:400000000 )   int n, m;   struct space {     int from, to, dist;     space(int f, int t) : from(f), to(t) {       if (f > t) {         dist = 0;       } else if (f == 1 || t == n) {         dist = t - f + 1;       } else {         dist = (t - f) / 2 + 1;       }     }     bool operator<(const space& b) const {       return dist > b.dist || dist == b.dist && from < b.from;     }   };   set<space> S;   int carP[1000010], carL[1000010], carR[1000010], posToCar[1000010];   int main() {     cin >> n >> m;     S.insert(space(1, n));     for (int i = 0; i < m + 1; i++) {       if (i == m) break;       int t, id;       cin >> t >> id;       if (t == 1) {         space sp = *S.begin();         S.erase(S.begin());         int F = sp.from, T = sp.to, pos;         if (F == 1 && T == n)           pos = 1;         else if (F == 1)           pos = 1;         else if (T == n)           pos = n;         else           pos = (F + T) / 2;         cout << pos << endl;         carP[id] = pos;         carL[id] = F - 1;         carR[id] = T + 1;         posToCar[pos] = id;         carR[posToCar[F - 1]] = pos;         carL[posToCar[T + 1]] = pos;         S.insert(space(F, pos - 1));         S.insert(space(pos + 1, T));       } else {         int F = carL[id], P = carP[id], T = carR[id];         S.erase(space(F + 1, P - 1));         S.erase(space(P + 1, T - 1));         carR[posToCar[F]] = T;         carL[posToCar[T]] = F;         S.insert(space(F + 1, T - 1));       }     }   }   