#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n,Q,a[N],p[N];
class Chair{
public:
    int cnt,rt[N];
    struct node{
        int ch[2],sum;
    }t[N<<5];
    #define ls(x) t[x].ch[0]
    #define rs(x) t[x].ch[1]
    void _mod(int &u,int v,int L,int R,int x,int w){
        u=++cnt;
        t[u]=t[v];
        t[u].sum+=w;
        if(L==R){
            return;
        }
        int mid=(L+R)>>1;
        x<=mid?_mod(ls(u),ls(v),L,mid,x,w):_mod(rs(u),rs(v),mid+1,R,x,w);
    }
    int _ask(int u,int L,int R,int l,int r){
        if(!u)return 0;
        if(L>=l&&R<=r)return t[u].sum;
        int mid=(L+R)>>1;
        int tot=0;
        if(l<=mid)tot+=_ask(ls(u),L,mid,l,r);
        if(r>mid)tot+=_ask(rs(u),mid+1,R,l,r);
        return tot;
    }
    void Modify(int x,int y,int p,int w){
        _mod(rt[x],rt[y],1,n,p,w);
    }
    int Query(int x,int l,int r){
        return _ask(rt[x],1,n,l,r);
    }
}T;
vector<pair<int,int> > h[N];
int ZZ;
ll Solve(int l,int r){
    int c=T.Query(r,l,n);
    int t=p[n];
    if(t>=l&&t<=r){
        t=l+r-t;
    }
    return 1LL*(c+ZZ+1)*n-(n-t);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>Q;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        p[a[i]]=i;
    }
    for(int i=1;i<n;++i){
        if(p[i]<p[i+1]){
            h[p[i+1]].emplace_back(p[i],1);
        }
        else{
            ++ZZ;
            h[p[i]].emplace_back(p[i+1],-1);
        }
    }
    for(int i=1;i<=n;++i){
        T.rt[i]=T.rt[i-1];
        for(auto [x,w]:h[i]){
            T.Modify(i,i,x,w);
        }
    }
    cout<<1LL*(ZZ+1)*n-(n-p[n])<<'\n';
    while(Q--){
        int l,r;
        cin>>l>>r;
        cout<<Solve(l,r)<<'\n';
    }
    return 0;
}