#include <fstream>

using namespace std;

int v[10005];
int n;
int poz[10005][12];
int minpoz[10000005];
int nr[10000005];

void caut_poz()
{
    for(int i = 1; i<=n+1; i++)
    {
        for(int j = 0; j<=9; j++)
        {
            poz[i][j] = n+1;
        }
    }

    for(int i = 1; i<=n; i++)
    {
        for(int j = i; j<=n; j++)
        {
            if(poz[i][v[j]] == n+1)
            {
                poz[i][v[j]] = j;
            }
        }
    }
}

void caut_min_poz()
{
    for(int i = 0; i<=9; i++)
    {
        minpoz[i] = poz[1][i];
    }
    for(int i = 10; i<=10000000; i++)
    {
        minpoz[i] = poz[minpoz[i/10]][i%10];
    }
}

void caut_nr()
{
    if(minpoz[0] == n+1)
    {
        nr[0] = 0;
    }
    else
    {
        nr[0] = 1;
    }


    for(int i = 1; i<=10000000; i++)
    {
        if(minpoz[i] != n+1)
        {
            nr[i] = nr[i-1] + 1;
        }
        else
        {
            nr[i] = nr[i-1];
        }
    }
}

int main()
{
    ifstream f("subsir.in");
    ofstream g("subsir.out");
    int c;
    f>>c>>n;

    for(int i = 1; i<=n; i++)
    {
        f>>v[i];
    }

    caut_poz();
    caut_min_poz();
    caut_nr();

    int num;

    if(c == 1)
    {
        f>>num;
        while(num--)
        {
            int x, y;
            f>>x>>y;

            if(minpoz[x] <= y)
            {
                g<<1<<"\n";
            }
            else
            {
                g<<0<<"\n";
            }
        }
    }
    else
    {

        f>>num;
        while(num--)
        {
            int x, y;
            f>>x>>y;

            if(x > 0)
            {
                g<<nr[y] - nr[x-1]<<"\n";
            }
            else
            {
                g<<nr[y]<<"\n";
            }

        }
    }

    return 0;
}