#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

const int N=2e3+,M=4e6+,inf=1e9+;

int sum[N][N];

int a[N];

int main()

{

    int n,m,t;

    scanf("%d%d",&n,&m);

    for(int i=; i<=n; i++)

        scanf("%d",&a[i]);

    for(int i=; i<=n; i++)

    {

        for(t=; t<=m; t++)

            sum[t][i]=sum[t][i-];

        sum[a[i]][i]=sum[a[i]][i-]+;

    }

    int q;

    scanf("%d",&q);

    while(q--)

    {

        int l,r,ans=;

        scanf("%d%d",&l,&r);

        for(int i=;i<=m;i++)

        if(sum[i][r]-sum[i][l-]>)

        ans++;

        printf("%d\n",ans);

    }

    return ;

}