#include <iostream>
using namespace std;
const int p=3e7,q=1e6;
		struct node
		{
			int l,r;
			int ls,rs;
			int sum;
		};
		node t[p+5];
		int cur,root[q+5];
		inline int mid(int l,int r)
		{
			return (l+r)/2;
		}
		inline void create(int id)
		{
			if(t[id].l!=t[id].r&&t[id].ls==0&&t[id].rs==0)
			{
				cur++;
				t[id].ls=cur;
				t[t[id].ls].l=t[id].l;
				t[t[id].ls].r=mid(t[id].l,t[id].r);
				cur++;
				t[id].rs=cur;
				t[t[id].rs].l=mid(t[id].l,t[id].r)+1;
				t[t[id].rs].r=t[id].r;
			}
		}
		void change_(int hid,int id,int x,int delta)
		{
			t[id].sum+=delta; 
			if(t[id].l==t[id].r&&t[id].l==x)
				return ;
			create(hid);
			if(x<=mid(t[id].l,t[id].r))
			{
				t[id].rs=t[hid].rs;
				cur++;
				t[id].ls=cur;
				t[cur].l=t[id].l;
				t[cur].r=mid(t[id].l,t[id].r);
				t[cur].sum=t[t[hid].ls].sum;
				change_(t[hid].ls,t[id].ls,x,delta);
			}
			else
			{
				t[id].ls=t[hid].ls;
				cur++;
				t[id].rs=cur;
				t[cur].l=mid(t[id].l,t[id].r)+1;
				t[cur].r=t[id].r;
				t[cur].sum=t[t[hid].rs].sum;
				change_(t[hid].rs,t[id].rs,x,delta);
			}
		}
		int request1(int lid,int rid,int x,int s)
		{
			if(t[lid].l==t[lid].r)
				return t[lid].l;
			create(lid);
			create(rid);
			if(s-t[t[rid].ls].sum+t[t[lid].ls].sum>=x)
				return request1(t[lid].rs,t[rid].rs,x,s-t[t[rid].ls].sum+t[t[lid].ls].sum);
			return request1(t[lid].ls,t[rid].ls,x,s);
		}
		int request2(int lid,int rid,int x,int s)
		{
			if(t[lid].l==t[lid].r)
				return t[lid].l;
			create(lid);
			create(rid);
			if(s-t[t[rid].rs].sum+t[t[lid].rs].sum>=x)
				return request2(t[lid].ls,t[rid].ls,x,s-t[t[rid].rs].sum+t[t[lid].rs].sum);
			return request2(t[lid].rs,t[rid].rs,x,s);
		}
		int request_(int id,int l,int r)
		{
			if(t[id].l==l&&t[id].r==r)
				return t[id].sum;
			create(id);
			int mid_=mid(t[id].l,t[id].r);
			bool f1=l<=mid_,f2=mid_+1<=r;
			if(f1&&!f2)
				return request_(t[id].ls,l,r);
			else if(!f1&&f2)
				return request_(t[id].rs,l,r);
			else if(f1&&f2)
				return request_(t[id].ls,l,mid_)+request_(t[id].rs,mid_+1,r);
		}
		inline void build(int minium,int maxium)
		{
			cur++;
			root[0]=cur;
			t[cur].l=minium;
			t[cur].r=maxium;
		}
		inline void change(int hid,int id,int x,int delta)
		{
			cur++;
			t[cur].l=t[root[0]].l;
			t[cur].r=t[root[0]].r;
			t[cur].sum=t[root[hid]].sum;
			root[id]=cur;
			change_(root[hid],root[id],x,delta);
		}
		inline int request1(int lid,int rid,int x)
		{
			return request1(root[lid],root[rid],x,t[root[rid]].sum-t[root[lid]].sum);
		}
		inline int request2(int lid,int rid,int x)
		{
			return request2(root[lid],root[rid],x,t[root[rid]].sum-t[root[lid]].sum);
		}
		inline int request(int id,int l,int r)
		{
			return request_(root[id],l,r);
		}
int n,m;
int a[500005];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,n);
	for(int i=1;i<=n;i++)
		change(i-1,i,a[i],1);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		int a=request1(l-1,r,(r-l+2)/2);
		int b=request2(l-1,r,(r-l+2)/2);
		if(a==b&&request(r,a,a)-request(l-1,a,a)>=(r-l+3)/2)
			cout<<a<<"\n";
		else
			cout<<0<<"\n";
	}
	return 0;
}

评测记录