Eva

Description

Input

Output

Sample Input

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

Sample Output

3
0
3
2
4

HINT

/**************************************************************

    Problem: 3339

    User: ictsing

    Language: C++

    Result: Accepted

    Time:2372 ms

    Memory:28648 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int mt=1000000+5;

int col[mt],cnt[mt],ans;

int pos[mt];

struct que{

  int lft,rgt,ans,id;

}qq[mt];

bool cmp(que a,que b)

{

    return pos[a.lft]<pos[b.lft]||(pos[a.lft]==pos[b.lft]&&a.rgt<b.rgt);

}

void update(int x)

{

    cnt[x]++;

    if(ans==x) while(cnt[ans]) ans++;

}

void delite(int x)

{

    cnt[x]--;

    if(!cnt[x]) ans=min(ans,x);

}

inline int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

int main()

{

    int n=read(),q=read(),sz=(int)sqrt((double)n*1.0);

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

        col[i]=read(),pos[i]=(i-1)/sz;

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

        qq[i].lft=read(),qq[i].rgt=read(),qq[i].id=i;

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

    int L=1,R=0;ans=0;

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

    {

        while(qq[i].rgt>R) R++,update(col[R]);

        while(qq[i].lft<L) L--,update(col[L]);

        while(qq[i].lft>L) delite(col[L]),L++;

        while(qq[i].rgt<R) delite(col[R]),R--;

        qq[qq[i].id].ans=ans;

    }

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

    return 0;

}

/*

7 5

 

0 2 1 0 1 3 2

 

1 3

 

2 3

 

1 4

 

3 6

 

2 7

 

3

 

0

 

3

 

2

 

4

*/