#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long LL;
int m=1;//离散化
typedef struct{
    int c[1005];
    void clear(){
        memset(c,0,sizeof(c));
    }
    void add(int x,int a){
        for(int i=x;i<=m;i+=lowbit(i)) c[i]+=a;
    }
    int get(int x){
        int Ret=0;
        for(int i=x;i>=1;i-=lowbit(i))
            Ret+=c[i];
        return Ret;
    }
}BiT;
typedef struct Query{
    int L,R,id;
    friend bool operator < (Query A,Query B){
        int tmp1=A.L/30,tmp2=B.L/30;
        if(tmp1!=tmp2) return tmp1<tmp2;
        return A.R<B.R;
    }
}Query;
Query Q[100005];
BiT T;
int n,a[1005],b[1005];
map<int,int> mp;
void f(){
    for(map<int,int>::iterator it = mp.begin();it!=mp.end();it++)
    {
        (*it).second=++m;
    }
    for(int i=1;i<=n;i++) a[i]=mp[a[i]];
}
int ret=0,cnt=0;
void addRight(int l,int r){
    for(int i=l;i<=r;i++){
        ret+=cnt-T.get(a[i]);
        T.add(a[i],1);
        cnt++;
    }
}
void addLeft(int l,int r){
    for(int i=r;i>=l;i--){
        ret+=T.get(a[i]-1);
        T.add(a[i],1);
        cnt++;
    }
}
void subRight(int l,int r){
    for(int i=r;i>=l;i--){
        ret-=cnt-T.get(a[i]);
        T.add(a[i],-1);
        cnt--;
    }
}
void subLeft(int l,int r){
    for(int i=l;i<=r;i++){
        ret-=T.get(a[i]-1);
        T.add(a[i],-1);
        cnt--;
    }
}
int ans[100005];
int main(){
    T.clear();
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        mp[a[i]]=0;
    }
    f();
    for(int i=0;i<q;i++) {
        scanf("%d%d",&Q[i].L,&Q[i].R);
        Q[i].id=i;
    }
    sort(Q,Q+q);
    addRight(Q[0].L,Q[0].R);
    ans[Q[0].id]=ret;
    for(int i=1;i<q;i++){
        if(Q[i].L<Q[i-1].L) addLeft(Q[i].L,Q[i-1].L-1);
        if(Q[i].L>Q[i-1].L) subLeft(Q[i-1].L,Q[i].L-1);
        if(Q[i].R<Q[i-1].R) subRight(Q[i].R+1,Q[i-1].R);
        if(Q[i].R>Q[i-1].R) addRight(Q[i-1].R+1,Q[i].R);
        ans[Q[i].id]=ret;
    }
    for(int i=0;i<q;i++)
        printf("%d\n",ans[i]);
    return 0;
}