#include <iostream>
#include <algorithm>
#include <queue>



using namespace std;

int main()
{
    ios_base::sync_with_stdio();
    cin.tie(NULL); cout.tie(NULL);

    long long n, m;
    cin >> n >> m;
    int mat[40][n+1];
    int niz[n];
    for (int i = 0; i<40; i++){
        mat[i][0]=0;
        niz[i]=0;
        }
    long long a[n];
    for (int i = 1; i<n+1; i++){
        cin >> a[i];
        int r=0;

        while((niz[r]!=0 && niz[r]!=a[i]) && r<39){
            r++;
        }
        niz[r]=a[i];
        for(int j = 0; j<40; j++){
            if (j==r){
                mat[j][i]=mat[j][i-1]+1;
            }
            else{
                mat[j][i]=mat[j][i-1];
            }
        }
    }
    for (int i = 0; i<40; i++){
        cout << niz[i] << "    ";
        for (int j = 0; j<n+1; j++){
            cout << mat[i][j] << " ";
        }
        cout << endl;
    }
    for (int i= 0; i<m; i++){
        int x, y;
        cin >> x >> y;
        int maxi = 0;
        for (int j = 0; j<35;j++){
            maxi = max(maxi, mat[j][y]-mat[j][x-1]);
        }
        cout << maxi << endl;
    }

    return 0;
}