#include <iostream>
#include <cstring>
#include <cstdio>
//#include <vector>

using namespace std;


int cap[65][100005];
int lastCap[65];
bool exist[65];
int n, k, lbl = 0;

//vector < int > map;  


FILE *fin = fopen("knjige.in", "r");
FILE *fout = fopen("knjige.out", "w");

/*
void swap(int &x, int &y)
{
    int t = x;
    x = y;
    y = t;
}
*/

int ccap(int tmp, int i)
{
    if (i == 0)
        return 0;
    if (cap[tmp][i] != 0)
        return cap[tmp][i];
        
    cap[tmp][i-1] = ccap(tmp, i-1);
    return cap[tmp][i-1];
}

int solve(int p, int q)
{
    int sum = 0;
    for (int i = 1; i <= lbl; i++) 
        if ( exist[i] )
        {
            cap[i][q] = ccap(i, q);
            cap[i][p-1] = ccap(i, p-1);
            if ( cap[i][q] > cap[i][p-1] )
                sum++;
        }
    return sum;
}
/*
int Idx(int x)
{
    int i = -1, j = map.size(), m; 
    if (j == 0) 
        return -1;
    while (i < j-1)
    {
        m = (i+j) / 2;                          //cout << m << endl;
        if (x < map[m])
            j = m;
        else if (x > map[m])
            i = m;
        else
            return m;
    }
    return -1;
}
*/
/*
void add(int x)
{
    int idx = Idx(x);                       //cout << "-=---------" << endl;
    if (idx == -1)
    {    
        idx = map.size();
        map.push_back(x);
        while (map[idx] < map[idx-1]) {
            swap( map[idx], map[idx-1] );
            idx--;
            if (idx == -1)
                break;
        }
    }
}
*/
int main () 
{   
    memset(cap, 0, sizeof(cap));
    memset(exist, 0, sizeof(exist));
    memset(lastCap, 0, sizeof(lastCap));
    //map.clear();

    
    fscanf(fin, "%d %d", &n, &k);
 /*   for (int i = 0; i < n; i++)
    {
        fscanf(fin, "%d", &glb[i]);
        if (tmp > lbl) 
            lbl = tmp;
    }
    
    if (lbl <= 60) 
    {
        int cap[][];
*/    
    for (int i = 1; i <= n; i++) 
    {
        int tmp;
        fscanf(fin, "%d", &tmp);
        if (tmp > lbl) 
            lbl = tmp;
        exist[tmp] = true;
        cap[tmp][i] = lastCap[tmp] + 1;
        lastCap[tmp] = cap[tmp][i];
    } // O(N)
    
    for (int i = 0; i < k; i++)
    {
        int p, q;
        fscanf(fin, "%d %d", &p, &q);
    //    cout << solve(p, q) << endl; // O(maxA * k)
        fprintf(fout, "%d\n", solve(p, q));
    }
    
    fclose(fin);
    fclose(fout);

 //   system("PAUSE");
    return 0;    
}  
