[BOJ] 16043 : Missing Gnomes

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, c[100001];
vector<int> a, b, r;

int main() {
    scanf("%d %d", &n, &m);
    a.resize(m+1);
    for (int i = 0, x; i < m; i++) {
        scanf("%d", &a[i]);
        c[a[i]] = 1;
    }
    for (int i = 1; i <= n; i++) {
        if (!c[i]) b.push_back(i);
    }

    int i = 0, j = 0;
    for (; i < m; i++) {
        for (; j < n-m; j++) {
            if (a[i] < b[j]) break;
            r.push_back(b[j]);
        }
        r.push_back(a[i]);
    }
    for (; j < n-m; j++) {
        r.push_back(b[j]);
    }

    for (int it : r) {
        printf("%d\n", it);
    }

    return 0;
}