牛牛的mex

题目分析：题目说要求未出现的最小自然数，并且题目有条件，那就是元素值都小于n并且互不相等，那么我们可以维护一个前缀和最小值和一个后缀和最小值，最后未出现的最小自然数就在区间旁边取一个最小值就行。

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

const int maxn = 1e5 + 10;
int a[maxn], f[maxn], w[maxn];

int main()
{
    int l, r, n, q;
    scanf("%d%d", &n, &q);
    f[0] = w[n + 1] = n; //初始化
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) //维护一个前缀和最小值
        f[i] = min(f[i - 1], a[i]);
    for (int i = n; i >= 1; --i) //维护一个后缀和最小值
        w[i] = min(w[i + 1], a[i]);
    for (int i = 1; i <= q; ++i)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", min(f[l - 1], w[r + 1])); //未出现的自然数最小值就在两边产生
    }
    return 0;
}