#include "permutation.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> encode(vector<int> p) {
    int n = p.size();
    vector<bool> used(n+1, 0);
    vector<int> encoded(n);
    int cur = 1; 

    for (int i = 0; i < n; i++) {
        if (p[i] == cur) {
            encoded[i] = -1;
            used[cur] = 1;
            while (cur <= n && used[cur]) cur++;
        } else {
            encoded[i] = p[i];
            used[p[i]] = 1;
            while (cur <= n && used[cur]) cur++;
        }
    }
    return encoded;
}


vector<int> decode(vector<int> encoded) {
    int n = encoded.size();
    vector<bool> used(n+1, 0);
    vector<int> decoded(n);
    int cur = 1;

    for (int i = 0; i < n; i++) {
        if (encoded[i] == -1) {
            while (cur <= n && used[cur]) cur++;
            decoded[i] = cur;
            used[cur] = 1;
        } else {
            decoded[i] = encoded[i];
            used[encoded[i]] = 1;
        }
    }
    return decoded;
}
