牛牛的mex

链接：https://ac.nowcoder.com/acm/contest/7079/A
思路：
让求在这个区间的最小未出现的最小自然数，那么可以反向思维来求不在这个区间出现的最小自然数。那么维护一个前缀和后缀最小值即可。
代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int a[maxn];
int sm[maxn], bm[maxn];
int main()
{
    int n, q;
    cin >> n >> q;
    sm[0] = n; bm[n+1] = n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sm[i] = min(sm[i-1], a[i]);
    }
    for(int i = n; i >= 1; i--){
        bm[i] = min(bm[i+1], a[i]);
    }
    int l, r;
    for(int i = 1; i <= q; i++){
        cin >> l >> r;
        cout << min(sm[l-1], bm[r+1]) << endl;
    }
}