// ROOT : DRAGON3012009 : WA in Real Life
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
#define FORD(i,r,l) for(int i = r ; i >= l ; i --)
#define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
#define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
#define ll long long
#define el "\n"
#define fi first
#define se second
#define _ROOT_ int main()
#define M 1000000007
#define MAXN 1000001
#define INF (1ll<<30)
#define BLOCK 425
#define NAME "file"
#define debug(a) cout << #a << " = " << a << endl;
using namespace std;

ll n, m, q ;
ll a[MAXN] ;
ll res[MAXN ] ;
ll mp[MAXN ] ;
vector<ll> pos[MAXN ] ;
vector<ll> cpr ;
vector<pair<ll,ll> > que[MAXN ] ;
vector<ll> big ;

struct Seg {
    ll val[MAXN << 2 ] ;
    void update(ll id, ll l, ll r, ll pos, ll value ) {
        if(l == r ) val[id] = max(val[id], value ) ;
        else {
            ll m = l + r >> 1 ;
            if(m >= pos ) update(id << 1, l, m, pos, value ) ;
            else update(id << 1 | 1, m + 1, r, pos, value ) ;
            val[id] = max(val[id << 1], val[id << 1 | 1 ]) ;
        }
    }

    ll get(ll id, ll l, ll r, ll u, ll v ) {
        if(u > r || v < l ) return 0 ;
        if(u <= l && v >= r ) return val[id] ;
        ll m = l + r >> 1 ;
        return max(get(id << 1, l, m,u, v ), get(id << 1 | 1, m + 1, r, u, v )) ;
    }
} seg ;


void init() {
    cin >> n >> q ;
    FOR(i, 1, n ) cin >> a[i] ;
    FOR(i, 1, n ) cpr.push_back(a[i]) ;
    compare(cpr) ;
    FOR(i, 1, n ) a[i] = lower_bound(cpr.begin(), cpr.end(), a[i] ) - cpr.begin() + 1 ;
    FOR(cnt, 1, q ) {
        ll l, r ;
        cin >> l >> r ;
        que[l].push_back({r, cnt } ) ;
    }
}

void solve() {
    FORD(i, n, 1 ) {
        pos[a[i]].push_back(i) ;
        if(pos[a[i]].size() < BLOCK  ) {
        for(ll v : pos[a[i]] ) seg.update(1 , 0 , n , v , v - i ) ;
        }else if(!mp[a[i]]&& pos[a[i]].size() >= BLOCK)
        {
        mp[a[i]] = true ;
        big.push_back(a[i]);
        }
        for(auto [r , id ] : que[i] ) {
            ll ans = seg.get(1 , 0 , n , i , r ) ;
            for(ll v : big ) {
                auto it = upper_bound(pos[i].begin() , pos[i].end() , r ) ;
                if(it == pos[i].begin() ) continue ;
                ans = max(ans , abs( *prev(it) - pos[i][0] ) ) ;
            }
            res[id] = ans ;
        }
    }
    FOR(i , 1 , q ) cout << res[i] << el ;
}

_ROOT_ {
    // freopen(NAME".inp" , "r" , stdin);
    // freopen(NAME".out" , "w", stdout) ;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1; // cin >> t ;
    while(t--) {
        init();
        solve();
    }
    return (0&0);
}