#include<bits/stdc++.h>
using namespace std;
int n;
int c[5010]={0};
 
int da(int x,int y,int z)
{
    int i,ans;
    ans=1;
    if(z>n)
    {
        return 0;
    }
    for(i=x;i<=y;i++)
    {
        if(c[i-1]>=z&&c[i]<z)
        {
            ans++;
        }
    }
    if(c[y]<z)
    {
        ans--;
    }
    return da(x,y,z+1)+ans;
}
int main()
{
    freopen("dry.in","r",stdin);
    freopen("dry.out","w",stdout);
    int q,a,b,i;
    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        cin>>c[i];
    }
    for(i=1;i<=q;i++)
    {
        cin>>a>>b;
        cout<<da(a,b,1)<<endl;
    }
    return 0;
}