A 牛牛的mex

题意：给一个 到 的长为 的排列 ，多次询问，每次给出 ，问 。

做一个前缀最小值和后缀最小值，每次询问比一下即可。

#include <bits/stdc++.h>
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, q, a[100005], mini1[100005], mini2[100005];
void init(){
    n = read(), q = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    mini1[0] = n;
    for (int i = 1; i <= n; ++i)
        mini1[i] = min(mini1[i - 1], a[i]);
    mini2[n + 1] = n;
    for (int i = n; i >= 1; --i)
        mini2[i] = min(mini2[i + 1], a[i]);
}
void solve(){
    while (q--){
        int l = read(), r = read();
        printf("%d\n", min(mini1[l - 1], mini2[r + 1]));
    }
}
int main(){
    init();
    solve();
    return 0;
}