#include<bits/stdc++.h>
#include"perm.h"
using namespace std;
 
void init(int c, int t) {}
int query(int l, int r);
 
 
std::vector<int> perm(int n) {
	vector<int> A(n + 1, 0), B(n + 1, 0);
	
	B[0] = n;   // 后缀 [0, n - 1] 最小的没出现过的值为 n - 1 
	A[n - 1] = n;  // 前缀 [0, n - 1] 最小的没出现过的值为 n - 1 
	int pzero = n - 1; 
	
	for (int l = 1; l <= n - 1; l ++) {  // 从小到大处理后缀 
        int v = query(l, n - 1);
        if (v == 0) {
        	// 一旦出现 0，后面的后缀都是 0 
            pzero = l - 1;  
            // 第一次出现 0，代表着第一次将 0 排在外面
			// 所以上一个位置就是 0 
            break;
        }
        B[l] = v;
    }
    
    for (int r = n - 2; r >= pzero; r --) {
        A[r] = query(0, r);   // 前缀从大到小，到 0 后的前缀 mex 都是 0 
    }
	
	vector<int> p(n, -1);   // 这里要是打成 n + 1 绝对判你错 
	set<int> unused;
	unused.clear();
	for (int i = 0; i < n; i ++) {
		unused.insert(i);
	}
	for (int i = 0; i < n; i ++) {
		int x = -1;
		if (i > 0 && A[i - 1] < A[i]) {
			x = A[i - 1];
		}
		if (i < n - 1 && B[i] > B[i + 1]) {
			x = B[i + 1];
		}
		if (x != -1) {
			unused.erase(x);
			p[i] = x;
		}
	}
	
	for (int i = 0; i < n; i ++) if (p[i] == -1) {
		int lef = 0, rig = 0;
		if (i != 0) lef = A[i - 1];
		if (i != n - 1) rig = B[i + 1];
		int x = max(lef, rig);
		auto it = unused.lower_bound(x);
		p[i] = *it;
		unused.erase(it);
	}
	
	return p;
}