#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;
const int maxn=1100,maxQ=100100;

int a[maxn],C[maxn],n;
void add(int x,int v){ while(x<=n){ C[x]+=v; x+=(x&-x); } }
int get(int x){ int ans=0; while(x){ ans+=C[x]; x-=(x&-x); } return ans; }
struct item{
    int l,r,id;
    bool operator<(const item &rhs)const{return l<rhs.l;}
}nxd[maxn*maxn],quest[maxQ];
int ans[maxQ];

int main() {
    int q;scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(int i=0;i<q;++i)scanf("%d%d",&quest[i].l,&quest[i].r),quest[i].id=i;
    int nxc=0;
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            if(a[i]>a[j]){
                nxd[nxc].l=i;
                nxd[nxc].r=j;
                ++nxc;add(j,1);
            }
    sort(nxd,nxd+nxc);
    sort(quest,quest+q);
    int pos=0;
    for(int i=0;i<q;++i){
        while(pos<nxc && nxd[pos].l<quest[i].l){ add(nxd[pos].r,-1);++pos; }
        ans[quest[i].id]=get(quest[i].r);
    }
    for(int i=0;i<q;++i)printf("%d\n",ans[i]);
}