#include <bits/stdc++.h>
using namespace std;
#define SC               scanf
#define PF               printf
#define ull              unsigned long long
#define ld               long double
#define F                first
#define S                second
#define pb               push_back
#define sort_a(a)        sort(a.begin(),a.end());
#define sort_d(a)        sort(a.rbegin(),a.rend());
#define READ(f)          freopen(f, "r", stdin)
#define WRITE(f)         freopen(f, "w", stdout)
#define rev(s)           reverse(s.begin(),s.end())
#define P(ok)            cout << (ok ? "YES\n": "NO\n")
#define __Heart__              ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define ll long long
typedef pair< ll, ll>                   PII;
const int mx = 3e5 + 5;
int K , Ans[mx], arr[mx],freq[mx] , F[mx] ;
struct Query
{
    int index, l, r ;
    bool operator < (const Query &other)const
    {
        int block_own = l/ K ;
        int block_other = other.l / K ;
        return(block_other == block_own) ? r < other.r : block_own < block_other ;
    }

} query[mx];
void add(int index)
{
    freq[arr[index]]++ ;
}
void remove (int index)
{
   freq[arr[index]]-- ;
}
void solve()
{
    int n , q ; cin >> n >> q ;
    for(int i = 0 ; i < n ; i++) cin >> arr[i] ;
    K = sqrt(n) ;
    for(int i = 0 ; i < q ; i++) cin >> query[i].l >> query[i].r , query[i].index = i  , query[i].l-- , query[i].r--;
    sort(query , query + q) ;
    int l = 0, r = -1 ;
    default_random_engine rd;
    for(int i = 0 ; i < q ; i++)
    {
        while(r < query[i].r) add(++r ) ;
        while(l < query[i].l) remove(l++) ;
        while(r > query[i].r) remove(r-- );
        while(l > query[i].l) add(--l) ;
        int val = INT_MAX;
        uniform_int_distribution <int> distribution(query[i].l , query[i].r);
        int low = (query[i].r - query[i].l + 1) /  3 ;
        for(int j = 0; j < 100; j++){
            int x = distribution(rd);
            if(freq[arr[x]] > low) val = min(val , arr[x]) ;
        }
        if(val == INT_MAX) val = -1;
        Ans[query[i].index] = val;
    }
    for(int i = 0 ; i < q ; i++) cout<< Ans[i] << "\n" ;
}
int main()
{
     __Heart__
    // READ("input7.txt") ;
   // WRITE("output7.txt") ;
     int t ; t = 1 ; while(t--) solve() ;
}