Manager

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <iomanip>
#include <fstream>
#include <string>
#include <set>
#include <deque>
#include <queue>
#include <map>
#include <bitset>
#include <random>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;
//typedef __int128 ultraint;
#define endl "\n"
#define sqrt sqrtl

//#define pow fast_pow

const ll inf = 1e17 + 13;
ld eps = 1e-6;
ll mod = 1e9 + 7;

auto cmp = [](const pair<ll, ll>& a, const pair<ll, ll>& b) -> bool {
    return a.first > b.first || (a.first == b.first && a.second < b.second);
};

signed main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, m, i, j, x;
    cin >> n >> m;
    set<pair<ll, ll>> mem1;
    set<pair<ll, ll>, decltype(cmp)> mem2(cmp);
    mem1.insert({ 1, n });
    mem2.insert({ n, 1 });
    vector<ll> mem(m, -1);
    vector <ll> bl(m);
    for (i = 0; i < m; i++) {
        cin >> x;
        if (x > 0) {
            bl[i] = x;
            if (!mem2.empty()) {
                ll len = mem2.begin()->first;
                ll pos = mem2.begin()->second;
                if (len >= x) {
                    mem2.erase(mem2.begin());
                    mem1.erase({ pos, len });
                    mem2.insert({ len - x, pos + x });
                    mem1.insert({ pos + x, len - x });
                    mem[i] = pos;
                }
            }
        }
        else {
            bl[i] = -inf;
            x = -x;
            x--;
            if (mem[x] != -1) {
                ll len = bl[x];
                ll pos = mem[x];
                auto sup = mem1.lower_bound({ pos, len });
                if (sup != mem1.begin()) {
                    auto it_prev = prev(sup);
                    ll pos_prev = it_prev->first;
                    ll len_prev = it_prev->second;
                    if (pos_prev + len_prev == pos) {
                        len += len_prev;
                        pos = pos_prev;
                        mem1.erase(it_prev);
                        mem2.erase({ len_prev, pos_prev });
                    }
                }
                if (sup != mem1.end()) {
                    ll pos_next = sup->first;
                    ll len_next = sup->second;
                    if (pos + len == pos_next) {
                        len += len_next;
                        mem1.erase(sup);
                        mem2.erase({ len_next, pos_next });
                    }
                }
                mem1.insert({ pos, len });
                mem2.insert({ len, pos });
            }
        }
    }
    for (i = 0; i < m; i++) {
        if (bl[i] != -inf) {
            cout << mem[i] << endl;
        }
    }
}