#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=100010,S=210,blk=510;
inline long long read(){
    long long r=0,i=getchar();
    while(i<'0'||i>'9')i=getchar();
    while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar();
    return r;
}
int n,q,a[N],b[blk][S],siz,bel[N],f2[blk][S][S],b2[blk][S][S],b3[blk][S][S],f3[blk][S],f4[blk][S];
long long f[blk][blk];
int book[N];
int cnt[blk][N],c[blk][S];
bool cst[S];
int bta[N];
inline void bta_add(int i,int k){while(i<=n)bta[i]+=k,i+=i&-i;}
inline int bta_get(int i){int r=0;while(i)r+=bta[i],i-=i&-i;return r;}
inline int B_B(int x,int y){
    int p1=1,res=0;
    for(int i=1;i<=b[y][0];i++){
        while(p1<=b[x][0]&&b[x][p1]<b[y][i])p1++;
        res+=b[x][0]-p1+1;
    }
    return res;
}
void init(){
    cin>>n>>q;
    siz=200;
    for(int i=1;i<=n;i++){
        a[i]=read();
        bel[i]=(i-1)/siz+1;
        cnt[bel[i]][a[i]]=1;
        b[bel[i]][++b[bel[i]][0]]=a[i];
        c[bel[i]][++c[bel[i]][0]]=a[i];
    }
    for(int i=1;i<=bel[n];i++){
        for(int j=1;j<=b[i][0];j++){
            for(int k=1;k<=j;k++)f2[i][k][j]=f2[i][k-1][j]+(b[i][k]>b[i][j]);
            f3[i][j]=f2[i][j][j]+f3[i][j-1];
        }
        for(int j=2;j<=n;j++)cnt[i][j]+=cnt[i][j-1];
        for(int j=1;j<=b[i][0];j++){
            bta_add(b[i][j],1);
            f[i][i]+=j-bta_get(b[i][j]);
        }
        for(int j=1;j<=b[i][0];j++)bta_add(b[i][j],-1);
        for(int j=b[i][0];j;j--){
            bta_add(b[i][j],1);
            f4[i][j]=f4[i][j+1]+bta_get(b[i][j]-1);
        }
        for(int j=1;j<=b[i][0];j++)bta_add(b[i][j],-1);
        sort(b[i]+1,b[i]+1+b[i][0]);
        for(int j=1;j<=b[i][0];j++)book[b[i][j]]=j;
    }
    for(int i=1;i<=bel[n];i++){
        memset(cst,0,sizeof(cst));
        for(int j=1;j<=c[i][0];j++){
            cst[book[c[i][j]]]=true;
            int u=0;
            for(int k=1;k<=c[i][0];k++)
                if(cst[k])b2[i][j][++u]=b[i][k];
        }
        memset(cst,0,sizeof(cst));
        for(int j=c[i][0];j;j--){
            cst[book[c[i][j]]]=true;
            int u=0;
            for(int k=1;k<=c[i][0];k++)
                if(cst[k])b3[i][j][++u]=b[i][k];
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=2;j<=bel[n];j++)cnt[j][i]+=cnt[j-1][i];
    for(int i=1;i<bel[n];i++)
        for(int j=i+1;j<=bel[n];j++)f[i][j]=f[i][j-1]+B_B(i,j);
    for(int i=1;i<=bel[n];i++){
        for(int j=1;j<b[i][0];j++){
            for(int k=j+2;k<=b[i][0];k++)f2[i][j][k]+=f2[i][j][k-1];
            f2[i][j][j]+=f2[i][j-1][j-1];
        }
    }
}
inline long long get_ans(int l,int r){
    long long res=0;
    int L=l-(bel[l]-1)*siz,R=r-(bel[r]-1)*siz;
    if(bel[l]==bel[r])return f2[bel[l]][R][R]-f2[bel[l]][L-1][L-1]-f2[bel[l]][L-1][R];
    res+=f4[bel[l]][L]+f3[bel[r]][R];
    int p=1;
    for(int i=1;i<=R;i++){
        while(p<=bel[l]*siz-l+1&&b3[bel[l]][L][p]<b2[bel[r]][R][i])p++;
        res+=bel[l]*siz-l-p+2;
    }
    if(bel[l]+1<bel[r])
        for(int i=l;i<=bel[l]*siz;i++)
            res+=cnt[bel[r]-1][a[i]-1]-cnt[bel[l]][a[i]-1];
    if(bel[l]+1<bel[r])
        for(int i=bel[r]*siz-siz+1;i<=r;i++)
            res+=cnt[bel[r]-1][n]-cnt[bel[l]][n]-cnt[bel[r]-1][a[i]]+cnt[bel[l]][a[i]];
    for(int i=bel[l]+1;i<bel[r];i++)res+=f[i][bel[r]-1];
    return res;
}
int main(){
//	freopen("C://read.in","r",stdin);
    init();
    long long lans=0;
    while(q--){
        long long l=read()^lans,r=read()^lans;
        lans=get_ans(l,r);
        printf("%lld\n",lans);
    }
    return 0;
}