主席树维护Mex。

每个右端点 r 维护出一棵 在[1, r ] 区间中 其他所有的 值离这个 r 最近的的位置是多少。

然后询问区间[L,R]的时候，从rt[R] 出发，然后如果左儿子的中所有出线位置的最小值 >= L, 则说明他们所有的点都出线在这个区间内了，然后往右走。

否则就说明左边有点没有出线过，需要往左走。

代码：

#include
      
       using namespace std;#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);#define LL long long#define ULL unsigned LL#define fi first#define se second#define pb push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lch(x) tr[x].son[0]#define rch(x) tr[x].son[1]#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair
       
         pll;const int inf = 0x3f3f3f3f;const int _inf = 0xc0c0c0c0;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL _INF = 0xc0c0c0c0c0c0c0c0;const LL mod =  (int)1e9+7;const int N =3e5+ 100;struct Node{    int ls, rs, mn, num;    Node(){ls = rs = mn = num = 0;}}tr[N<<5];int rt[N];int tot;int build(int l, int r){    int x = ++tot;    if(l == r) return x;    int m = l+r >> 1;    tr[x].ls = build(l,m);    tr[x].rs = build(m+1,r);    return x;}int Update(int L, int p, int lst, int l, int r){    int x = ++tot;    tr[x] = tr[lst];    if(l == r){        tr[x].mn = p;        ++tr[x].num;        return x;    }    int m = l+r >> 1;    if(L <= m) tr[x].ls = Update(L, p, tr[lst].ls, l, m);    else tr[x].rs = Update(L, p, tr[lst].rs, m+1, r);    tr[x].mn = min(tr[tr[x].ls].mn, tr[tr[x].rs].mn);    tr[x].num = tr[tr[x].ls].num + tr[tr[x].rs].num;    return x;}int Query(int L, int x, int x2){//    cout << L << ' ' << tr[x].mn << ' ' << tr[x].num - tr[x2].num << endl;    if(tr[x].mn >= L) return tr[x].num - tr[x2].num;    if(!tr[x].ls) return 0;    int ret = 0;    if(tr[tr[x].ls].mn >= L) ret = tr[tr[x].ls].num-tr[tr[x2].ls].num + Query(L,tr[x].rs,tr[x2].rs);    else ret = Query(L,tr[x].ls,tr[x2].ls);    return ret;}void Q(int p, int l, int r){    cout << l << " " << r <<  " " << tr[p].mn << ' ' << tr[p].num << endl;    if(l == r) return ;    int m = l+r >> 1;    Q(tr[p].ls, l, m);    Q(tr[p].rs, m+1, r);}int a[N];int main(){    int n, m;    scanf("%d", &n);    rt[0] = build(1,n);    for(int i = 1; i <= n; ++i){        scanf("%d", &a[i]);        if(a[i] <= n) rt[i] = Update(a[i], i, rt[i-1], 1, n);        else rt[i] = rt[i-1];    }//    Q(rt[4],1,n);    scanf("%d", &m);    int L, R;    for(int i = 1; i <= m; ++i){        scanf("%d%d", &L, &R);        printf("%d\n", (R-L+1)-Query(L, rt[R], rt[L-1]));    }    return 0;}