#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=2e5+5,siz=448,maxk=505;

struct Query_Node
{
    int l,r,kl,id;
    bool operator < (const Query_Node &x) const{
        return kl!=x.kl?kl<x.kl:(kl&1?kl<x.kl:kl>x.kl);
    }
}q[maxn];

int a[maxn],b[maxn],n,m,tot,nk,klen,ans[maxn];
int bel[maxn],L[maxk],R[maxk],bvis[maxk],vis[maxn],blocks;

namespace quick {
#define tp template<typename Type>
	namespace in {
		inline char getc() {
			static char buf[1<<21],*p1=buf,*p2=buf;
			return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
		}
		inline int read(char *s) {
			*s=getc();
			while(isspace(*s)) {*s=getc();if(*s==EOF) return 0;}
			while(!isspace(*s)&&*s!=EOF) {s++;*s=getc();}
			*s='\0'; return 1;
		}
		inline int read(char &c) {
			return (c=getc())!=EOF;
		}
		tp inline int read(Type &x) {
			x=0;bool k=false;char c=getc();
			while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
			while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
			x*=(k?-1:1); return 1;
		}
		template <typename Type,typename... Args>
		inline int read(Type &t,Args &...args) {
			int res=0;
			res+=read(t);res+=read(args...);
			return res;
		}
	}
	using in::read;
	namespace out {
		char buf[1<<21];int p1=-1;const int p2=(1<<21)-1;
		inline void flush() {
			fwrite(buf,1,p1+1,stdout);
			p1=-1;
		}
		inline void putc(const char &c) {
			if(p1==p2) flush();
			buf[++p1]=c;
		}
		inline void write(char *s) {
			while(*s!='\0') putc(*s),s++;
		}
		inline void write(const char *s) {
			while(*s!='\0') putc(*s),s++;
		}
		tp inline void write(Type x) {
			static char buf[30];int p=-1;
			if(x<0) {putc('-');x=-x;}
			if(x==0) putc('0');
			else for(;x;x/=10) buf[++p]=x%10+48;
			for(;p!=-1;p--) putc(buf[p]);
		}
		inline void write(const char &c) {putc(c);}
		template <typename Type,typename... Args>
		inline void write(Type t,Args ...args) {
			write(t);write(args...);
		}
	}
	using out::write;
	using out::flush;
	tp inline Type max(const Type &a,const Type &b) {
		if(a<b) return b;
		return a;
	}
	tp inline Type min(const Type &a,const Type &b) {
		if(a<b) return a;
		return b;
	}
	tp inline void swap(Type &a,Type &b) {
		a^=b^=a^=b;
	}
	tp inline Type abs(const Type &a) {
		return a>=0?a:-a;
	}
#undef tp
}
using namespace quick;

void init()
{
    klen=n/sqrt(m*2/3);
    blocks=(nk-1)/siz+1;
    for(int i=1;i<=blocks;++i)
        L[i]=R[i-1]+1,R[i]=i*siz;
    R[blocks]=nk;
    for(int i=1;i<=blocks;++i)
        for(int j=L[i];j<=R[i];++j)
            bel[j]=i;
}

void ins(int pos)
{
    if(a[pos]>nk) return;
    vis[a[pos]]++;
    if(vis[a[pos]]==1) bvis[bel[a[pos]]]++;
}

void del(int pos)
{
    if(a[pos]>nk) return;
    vis[a[pos]]--;
    if(!vis[a[pos]]) bvis[bel[a[pos]]]--;
}

int getans()
{
    if(!vis[1]) return 0;
    int pos=0,nowk=1;
    while(nowk<=blocks&&bvis[nowk]==siz) pos+=siz,++nowk;
    for(int i=L[nowk];i<=R[nowk]+1;++i)
        if(!vis[i]) {pos=i;break;}
    return b[pos-1]+1;
}

int main()
{
    read(n,m);
    for(int i=1;i<=n;++i)
        read(a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    tot=unique(b+1,b+n+1)-b-1;
    if(b[1])
    {
        for(int i=1;i<=m;++i) puts("0");
        return 0;
    }
    for(int i=2;i<=tot;++i)
        if(b[i]!=b[i-1]+1) {nk=i-1;break;}
    if(!nk) nk=tot;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    init();
    for(int i=1;i<=m;++i)
    {
        read(q[i].l,q[i].r);
        q[i].id=i;q[i].kl=(q[i].l-1)/klen+1;
    }
    sort(q+1,q+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;++i)
    {
        while(r<q[i].r) ins(++r);
        while(r>q[i].r) del(r--);
        while(l>q[i].l) ins(--l);
        while(l<q[i].l) del(l++);
        ans[q[i].id]=getans();
    }
    for(int i=1;i<=m;++i)
        write(ans[i],'\n');
    flush();
    return 0;
}