#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct lsh{long x,y;}e[1005];
bool cmp0(lsh a,lsh b) {return(a.x<b.x);}
struct Que{long l,r,lk,id;}Q[100005];
bool cmp(Que a,Que b) {return(a.lk<b.lk||a.lk==b.lk&&a.r<b.r);}
long a[1005],b[1005],vis[1005],prt[100005],n,ans;
long lowbit(long x) {return(x&-x);}
long query(long x) {long ans=0;while (x) {ans+=b[x];x-=lowbit(x);}return(ans);}
void modify(long x,long val) {while (x<=n) {b[x]+=val;x+=lowbit(x);}}
void work(long x,long f)
{
    if (vis[x]) {if (f) ans-=query(n)-query(a[x]); else ans-=query(a[x]-1);modify(a[x],-1);}
     else {if (f) ans+=query(n)-query(a[x]); else ans+=query(a[x]-1);modify(a[x],1);}
    vis[x]^=1;
}
int main()
{
    //freopen("b.in.txt","r",stdin);freopen("b.out.txt","w",stdout);
    long i,j,q,gn,L,R;
    scanf("%ld%ld",&n,&q);gn=(long)sqrt(n);
    for (i=1;i<=n;i++) {scanf("%ld",&e[i].x);e[i].y=i;}
    sort(e+1,e+n+1,cmp0);j=0;for (i=1;i<=n;i++) {if (e[i].x>e[i-1].x) j++;a[e[i].y]=j;}
    for (i=1;i<=q;i++) {scanf("%ld%ld",&Q[i].l,&Q[i].r);Q[i].id=i;Q[i].lk=(Q[i].l-1)/gn+1;}
    sort(Q+1,Q+q+1,cmp);L=1,R=0;
    for (i=1;i<=q;i++)
    {
        while (R<Q[i].r) work(++R,1);while (R>Q[i].r) work(R--,1);
        while (L<Q[i].l) work(L++,0);while (L>Q[i].l) work(--L,0);
        prt[Q[i].id]=ans;
    }
    for (i=1;i<=q;i++) printf("%ld\n",prt[i]);
    return 0;
}