#include<iostream>
#include<cstdio>
#include<cassert>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<vector> 
#include<cstring>
#include<string>
#include<map>
#include<set>

#define mp make_pair
#define scn second
#define frs first
#define pb push_back

#define NAME "volleyball"

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> pi;
const int P = 239017;
const ll INF = 10000000000000000ll;

         

void compress(int n, int* a) {
	vector<pi> b;
	for (int i = 0; i < n; ++i)
		b.pb(mp(a[i], i));
	sort(b.begin(), b.end());
	for (int i = 0, c = 0; i < n; ++i) {
		if (i > 0 && b[i].frs != b[i - 1].frs)
			++c;		
		a[b[i].scn] = c;
	}
}
const int MAXK = 20;

pi f[1 << MAXK][MAXK], g[1 << MAXK][MAXK];
int n, m, a[1000000];

int used[1000000];
                     
int fget(int i) {
	used[i] = 1;
	if (f[i][0].frs == i)
		return i;
	f[i][0].frs = fget(f[i][0].frs);
	f[i][0].scn = f[i][0].frs - i;
	return f[i][0].frs;

}

int gget(int i) {
	used[i] = 1;
	if (g[i][0].frs == i)
		return i;
	g[i][0].frs = gget(g[i][0].frs);
	g[i][0].scn = -g[i][0].frs + i;
	return g[i][0].frs;

}


int main(){
    freopen(NAME ".in", "r", stdin); 
    freopen(NAME ".out", "w", stdout); 

    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) 
    	scanf("%d", &a[i]);
    compress(n, a);
    vector<int> st;
    for (int i = 0; i < MAXK; ++i) 
    	for (int j = 0; j < n; ++j)
    		f[j][i] = g[j][i] = mp(-100, -100);
    
    for (int i = 0; i < n; ++i) {
    	f[i][0] = mp(i, 0);
    	while (st.size() > 0 && a[i] > a[st.back()])
    		st.pop_back();
    	if (st.size() > 0 && a[st.back()] == a[i]) {
    		f[st.back()][0] = mp(i, i - st.back());
    		st[st.size() - 1] = i;
    	}
    	else
    		st.pb(i);
    }
    

    st.clear();
    for (int i = n - 1; i >= 0; --i) {
    	g[i][0] = mp(i, 0);
    	while (st.size() > 0 && a[i] > a[st.back()])
    		st.pop_back();
    	if (st.size() > 0 && a[st.back()] == a[i]) {
    		g[st.back()][0] = mp(i, -i + st.back());
    		st[st.size() - 1] = i;
    	}
    	else
    		st.pb(i);
    }
    for (int i = 0; i < n; ++i)
    	if (!used[i])
    		fget(i);
    memset(used, 0, 1000000);
    for (int i = n - 1; i >= 0; --i)
    	if (!used[i])
    		gget(i);
    
    for (int k = 1; k < MAXK; ++k) {
    	for (int i = 0; i < n; ++i) {
    		pi a = f[i][k - 1];
    		if (a.frs + 1 == n || a.frs < 0)
    			continue;
    		pi b = f[a.frs + 1][k - 1];
    		f[i][k] = mp(b.frs, max(a.scn, b.scn));	

    	}	
    }

    for (int k = 1; k < MAXK; ++k) {
    	for (int i = n - 1; i >= 0; --i) {
    		pi a = g[i][k - 1];
    		if (a.frs - 1 == -1 || a.frs < 0)
    			continue;
    		pi b = g[a.frs - 1][k - 1];
    		g[i][k] = mp(b.frs, max(a.scn, b.scn));	
    	}	
    }
    /*for (int i = 0; i < MAXK; ++i)
    	for (int j = 0; j < n; ++j) {
    		cout << "g[" << j << "][" << i << "] = " << g[j][i].frs << "\n";

    	}
    return 0;*/
 	
   	for (int it = 0; it < m; ++it) {
    	int l, r;
        scanf("%d%d", &l, &r);
        --l, --r;
        int ans = 0;
        int now1 = l;
        for (int i = MAXK - 1; i >= 0; --i) {
       	    if (f[now1][i].frs > 0 && f[now1][i].frs <= r) {
       			ans = max(ans, f[now1][i].scn);
       			now1 = f[now1][i].frs + 1;
       			//cerr << now1 << " ";
       		}
       	
        }
        
        int now2 = r;        
        for (int i = MAXK - 1; i >= 0; --i) {
       		if (g[now2][i].frs >= 0 && g[now2][i].frs >= l) {
       			ans = max(ans, g[now2][i].scn);
       			now2 = g[now2][i].frs - 1;
       		}
        }                         
        
        while (f[now1][0].frs > 0 && f[now1][0].frs <= r) {
        	ans = max(ans, f[now1][0].scn);
       		now1 = f[now1][0].frs + 1;       	
       	}  

        while (g[now2][0].frs > 0 && g[now2][0].frs >= l) {
        	ans = max(ans, g[now2][0].scn);
       		now2 = g[now2][0].frs - 1;       	
        }  

        if (a[now2] == a[now1])
        	ans = max(now2 - now1, ans);
    	
    	printf("%d\n", ans);


    }

    return 0;
}



