Description

　　有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

Input

　　第一行n,m。

　　第二行为n个数。

　　从第三行開始，每行一个询问l,r。

Output

　　一行一个数，表示每一个询问的答案。

Sample Input

5 5

2 1 0 2 1

3 3

2 3

2 4

1 2

3 5

Sample Output

1

2

3

0

3

HINT

数据规模和约定

　　对于100%的数据：

　　1<=n,m<=200000

　　0<=ai<=109

　　1<=l<=r<=n

　　对于30%的数据：

　　1<=n,m<=1000

Source

By 佚名提供

同3339

仅仅只是加了离散化

(双倍经验 古人诚不欺我也

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define MAXN 200010

#define GET (ch>='0'&&ch<='9')

#define lchild rt<<1,l,mid

#define rchild rt<<1|1,mid+1,r

#define ln rt<<1

#define rn rt<<1|1

#define MAXINT 0x7fffffff

using namespace std;

int n,m,cnt,mex,now=1;

int a[MAXN],b[MAXN],next[MAXN],last[MAXN],sg[MAXN];

bool hash[MAXN];

void in(int &x)

{

    char ch=getchar();x=0;

    while (!GET)    ch=getchar();

    while (GET) x=x*10+ch-'0',ch=getchar();

}

struct seg

{

    int l,r,minn;

}tree[MAXN<<2];

struct Query

{

    int l,r,id,ans;

    bool operator <(const Query& a)const    {return l==a.l?

r<a.r:l<a.l;}

}q[MAXN];

bool cmp(Query a,Query b)   {return a.id<b.id;}

int find(int x)

{

    int l=1,r=cnt,mid=(l+r)>>1;

    while (l<=r)

    {

        mid=(l+r)>>1;

        if (b[mid]<x)   l=mid+1;

        else    r=mid-1;

    }

    return l;

}

void push_down(int rt)

{

    if (tree[rt].l==tree[rt].r) return;

    tree[ln].minn=min(tree[rt].minn,tree[ln].minn);tree[rn].minn=min(tree[rn].minn,tree[rt].minn);

}

void build(int rt=1,int l=1,int r=n)

{

    tree[rt].l=l;tree[rt].r=r;tree[rt].minn=MAXINT;

    if (l==r)   {tree[rt].minn=sg[l];return;}

    int mid=(l+r)>>1;build(lchild);build(rchild);

}

void modify(int rt,int l,int r,int delta)

{

    push_down(rt);

    int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1;

    if (l<=L&&r>=R) {tree[rt].minn=min(tree[rt].minn,delta);return;}

    if (r<=mid) modify(ln,l,r,delta);

    else    if (l>mid)  modify(rn,l,r,delta);

    else    modify(ln,l,mid,delta),modify(rn,mid+1,r,delta);

}

int query(int rt,int x)

{

    push_down(rt);

    int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1;

    if (L==R)   return tree[rt].minn;

    if (x<=mid) return query(ln,x);

    else    return query(rn,x);

}

int main()

{

    in(n);in(m);int x;

    for (int i=1;i<=n;i++)  in(a[i]),b[i]=a[i];

    sort(b+1,b+n+1);

    for (int i=1;i<=n;i++)  if (i==1||b[i]!=b[i-1]) b[++cnt]=b[i];

    for (int i=1;i<=n;i++)

    {

        x=find(a[i]);hash[x]=1;

        if (a[i]==mex)  for (;hash[x];) if (b[++x]!=++mex)  break;

        sg[i]=mex;

    }

    build();

    for (int i=n;i;i--) x=find(a[i]),next[i]=last[x],last[x]=i;

    for (int i=1;i<=m;i++)  in(q[i].l),in(q[i].r),q[i].id=i;

    sort(q+1,q+m+1);

    for (int i=1;i<=m;i++)

    {

        while (now<q[i].l)

        {

            if (!next[now]) next[now]=n+1;

            modify(1,now,next[now]-1,a[now]);now++;

        }

        q[i].ans=query(1,q[i].r);

    }

    sort(q+1,q+m+1,cmp);

    for (int i=1;i<=m;i++)  printf("%d\n",q[i].ans);

}