#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int i,j,m,n,p,k,a[1005],q,b[1005],tree[1005],l,r,ans[1005][1005];
int lowbit(int x) { return x&-x; }
int ask(int x) {
     int sum=0;
     for (;x;x-=lowbit(x)) sum+=tree[x];
     return sum;
}
int ins(int x)
{
      for (;x<=b[0];x+=lowbit(x)) tree[x]++;
}
int main()
{
     scanf("%d%d",&n,&q);
     for (i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
     sort(b+1,b+n+1);
     b[0]=unique(b+1,b+n+1)-(b+1);
     for (i=1;i<=n;++i) a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
     for (i=1;i<=n;++i)
     {
          memset(tree,0,sizeof(tree));
          for (j=i;j<=n;++j)
          {
               ans[i][j]=ans[i][j-1]+ask(b[0])-ask(a[j]);
               ins(a[j]);
          }
     }
     for (;q--;)
    {
         scanf("%d%d",&l,&r);
         printf("%d\n",ans[l][r]);
    }
}