#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;
}

首先考虑如果单组询问可以问 $2n$ 个问题怎么做。

显然，$\text{mex}$ 相当于“补集的最小值”，即 $[l, r]$ 的 $\text{mex}$ 相当于一段前缀和一段后缀的最小值。注意到这一点后，我们可以得出以下两条结论：

1. 任意区间 $\text{mex}$ 相同，等价于任意前缀或后缀的 $\min$ 相同。

2. 前缀 $\text{mex}$ 等于后缀 $\min$，反过来同理。

不妨考虑把所有前缀 $\text{mex}$ 和后缀 $\text{mex}$ 都问一遍，这样需要恰好 $2n$ 次询问，可以得到所有前缀 $\min$与后缀 $\min$。

接下来考虑构造。如果 $[0, l)$ 的 $\min$ 与 $[0, l]$ 的 $\min$ 不同，相当于确定了 $p_l$ 的值，并且给 $[0, l)$ 的数添加了一条限制。

因此，贪心地选择符合要求的数中最小的填上即可，使用你喜欢的数据结构维护。

下面考虑 $n + \log n$ 次怎么做。

如果把表打下来，会发现里面大量的 $0$ 是没用的（限制每个数 $\geq 0$ 是没意义的）。

因此，不妨先通过二分的方法找到 $0$ 的位置，然后左右分开查询 $\text{mex}$。

这样可以做到 $n + \log n$ 次查询。

最后考虑怎么把 $\log n$ 消掉。

注意到二分其实是没意义的，因为任选一段往后扫，得到有用信息（前后缀 $\min$）的同时可以判断是否找到 $0$。

因此可以去掉二分变成 $n$ 次询问，注意 $0$ 在两端的细节问题。

挂一份赛后默写的代码，过 qoj 数据了：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "perm.h"

using namespace std;
using namespace __gnu_pbds;

void init(int c, int t){
    // zhang_kevin
    return;
}

int premin[30005], sufmin[30005];

vector<int> perm(int n){
    vector<int> res(n, -1);
    memset(premin, 0xff, sizeof(premin)), memset(sufmin, 0xff, sizeof(sufmin));
    tree<int, null_type, less<int>, rb_tree_tag> t;
    for(int i = 0; i < n; i++) t.insert(i);
    int lst = n, zero; // query(0, n - 1) == n
    for(int i = n - 2; i >= 0 && lst; i--){
        int now = query(0, i);
        if(now != lst) res[i + 1] = sufmin[i + 1] = now, t.erase(now);
        lst = now;
        if(!lst) zero = i + 1;
    }
    lst = n;
    for(int i = 1; i <= (~zero ? zero + 1 : n - 1) && lst; i++){
        int now = 0;
        if(i <= zero) now = query(i, n - 1);
        if(now != lst) res[i - 1] = premin[i - 1] = now, t.erase(now);
        lst = now;
    }
    int cur = n;
    for(int i = 0; i < n; i++){
        if(~premin[i]) cur = premin[i];
        premin[i] = cur;
    }
    cur = n;
    for(int i = n - 1; i >= 0; i--){
        if(~sufmin[i]) cur = sufmin[i];
        sufmin[i] = cur;
    }
    for(int i = 0; i < n; i++){
        if(!~res[i]){
            auto it = t.lower_bound(max(premin[i], sufmin[i]));
            res[i] = *it, t.erase(it);
        }
    }
    return res;
}