蒟蒻主席树求助，90分RE#2

// by youyou2007 in 2022.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#define REP(i, x, y) for(int i = x; i < y; i++)
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define PER(i, x, y) for(int i = x; i > y; i--)
#define per(i, x, y) for(int i = x; i >= y; i--)
#define lc (k << 1)
#define rc (k << 1 | 1)
using namespace std;
/*
inline int read()
{
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
*/
const int N = 5E5 + 5;
const int LOG = 19;
int n, m;
int a[N], root[N], cnt;
struct node
{
	int l, r, sum;
}f[N * LOG];
void pushup(int k)
{
	f[k].sum = f[f[k].l].sum + f[f[k].r].sum; 
}
void build(int l, int r, int &k)
{
	if(!k)
	{
		k = ++cnt;
	}
	f[k].sum = 0;
	if(l == r)
	{
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, f[k].l);
	build(mid + 1, r, f[k].r);
	pushup(k);
}
void modify(int l, int r, int &k, int old_k, int q, int d)
{
	if(!k)
	{
		k = ++cnt;
	}
	f[k].sum = f[old_k].sum;
	if(l == r)
	{
		f[k].sum += d;
		return;
	}
	int mid = (l + r) / 2;
	if(q <= mid)
	{
		modify(l, mid, f[k].l, f[old_k].l, q, d);
		f[k].r = f[old_k].r;
	}
	else
	{
		modify(mid + 1, r, f[k].r, f[old_k].r, q, d);
		f[k].l = f[old_k].l;
	}
	pushup(k);
}
int query(int l, int r, int k, int old_k, int half)
{
	if(f[k].sum - f[old_k].sum <= half) return 0;
	if(l == r)
	{
		return l;
	}
	int mid = (l + r) / 2;
	int res1 = f[f[k].l].sum - f[f[old_k].l].sum;
	int res2 = f[f[k].r].sum - f[f[old_k].r].sum;
	if(res1 > half)
	{
		return query(l, mid, f[k].l, f[old_k].l, half);
	}
	else if(res2 > half)
	{
		return query(mid + 1, r, f[k].r, f[old_k].r, half);
	}
	else
	{
		return 0;
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	rep(i, 1, n)
	{
		scanf("%d", &a[i]);
	}
	build(1, n, root[0]);
	rep(i, 1, n)
	{
		modify(1, n, root[i], root[i - 1], a[i], 1);
	}
	while(m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", query(1, n, root[r], root[l - 1], (r - l + 1) / 2));
	}
	return 0;
}