// Author: wlzhouzhuan
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define mset(s,t) memset(s,t,sizeof(s))
#define mcpy(s,t) memcpy(s,t,sizeof(t))
#define SZ(x) ((int)x.size())
#define pb push_back
#define eb emplace_back
#define fir first
#define sec second

template<class T1,class T2>void ckmax(T1 &a,T2 b){if(a<b)a=b;}
template<class T1,class T2>void ckmin(T1 &a,T2 b){if(a>b)a=b;}

namespace IO {
  const int SIZE = 1 << 16;
  char ibuf[SIZE]; int iS, iT;
  char obuf[SIZE]; int oT;
  inline char gc() {
    if (iS == iT)
      iS = 0, iT = fread(ibuf, 1, SIZE, stdin);
    return iS == iT ? EOF : ibuf[iS++];
  }
  inline void pc(char c) {
    obuf[oT++] = c;
    if (oT == SIZE)
      fwrite(obuf, 1, SIZE, stdout), oT = 0;
  }
  inline int read() {
    int x = 0, f = 0;
    char c = gc();
    while (!isdigit(c)) f |= c == '-', c = gc();
    while (isdigit(c)) x = 10 * x + c - '0', c = gc();
    return f ? -x : x; 
  }
  inline void print(int64_t x) {
    static char bufn[64];
    int len = 0;
    if (x < 0) x = -x, pc('-');
    while (x >= 10) bufn[len++] = x % 10 + '0', x /= 10;
    bufn[len++] = x + '0';
    while (len--) pc(bufn[len]);
  }
  inline void print(int64_t x, char ch) {
    print(x), pc(ch);
  }
  struct ff {
    ~ff() {
      if (oT)
        fwrite(obuf, 1, oT, stdout);
    }
  } flusher;
}
using namespace IO;

const int N=5000005;

int n,m,be[N],a[N],pos[N],B;

struct Q{
    int l,r,id;
    friend bool operator < (const Q&a,const Q&b){
        return be[a.l]^be[b.l]?a.l<b.l:a.r>b.r;
    }
}q[N];

struct UNDO{
    int who,l,r;
}rec[N];
int rlen;
int tmpL[N],tmpR[N];
int L[N],R[N];
ll ANS[N];

pii brute[N];int blen;
ll BRUTE(int l,int r){
    ll ans=0;int las=0;
    rep(i,1,blen){
        if(brute[i].sec>=l&&brute[i].sec<=r){
            if(las)ans+=abs(las-brute[i].sec);
            las=brute[i].sec;
        }
    }
    return ans;
}

int main(){
    freopen("rrads.in","r",stdin);
    freopen("rrads.out","w",stdout);
    n=read(),m=read(),B=max(1,(int)(n/sqrt(m)));

    rep(i,1,n)a[i]=read(),pos[a[i]]=i,be[i]=(i-1)/B+1;
    rep(i,1,m)q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+m+1);
    int j=1;ll ans=0;
    rep(i,1,n){
        L[pos[i]]=pos[i-1],R[pos[i]]=pos[i+1];
        if(i<n)ans+=abs(pos[i]-pos[i+1]);
    }
    for(int l=1,r=B,zz=1;l<=n;l+=B,r+=B,zz++){
        ckmin(r,n);
        
        blen=0;rep(i,l,r)brute[++blen]={a[i],i};sort(brute+1,brute+blen+1);

        ll qaqans=ans;
        int cur=n;
        rep(i,1,n)tmpL[i]=L[i],tmpR[i]=R[i];
        while(j<=m&&be[q[j].l]==zz){
            
            if(be[q[j].r]==zz){
                ANS[q[j].id]=BRUTE(q[j].l,q[j].r);
                j++;
                continue;
            }

            while(cur>q[j].r){
                // del val
                bool ok1=L[cur],ok2=R[cur];
                if(ok1)ans-=abs(L[cur]-cur);
                if(ok2)ans-=abs(R[cur]-cur);
                if(ok1&&ok2)ans+=abs(L[cur]-R[cur]);
                R[L[cur]]=R[cur],L[R[cur]]=L[cur],cur--;
            }
            ll tmpans=ans;
            rep(cur,l,q[j].l-1){
                // del
                bool ok1=L[cur],ok2=R[cur];
                if(ok1)ans-=abs(L[cur]-cur);
                if(ok2)ans-=abs(R[cur]-cur);
                if(ok1&&ok2)ans+=abs(L[cur]-R[cur]);
                rec[++rlen]={cur,L[cur],R[cur]};
                R[L[cur]]=R[cur],L[R[cur]]=L[cur];
            }
            ANS[q[j].id]=ans;
            
            // undo
            ans=tmpans;
            while(rlen){
                int u=rec[rlen].who,ul=rec[rlen].l,ur=rec[rlen].r;
                R[ul]=u,L[ur]=u,rlen--;
            }

            j++;
        }

        ans=qaqans;
        rep(i,1,n)L[i]=tmpL[i],R[i]=tmpR[i];
        rep(cur,l,r){
            bool ok1=L[cur],ok2=R[cur];
            if(ok1)ans-=abs(L[cur]-cur);
            if(ok2)ans-=abs(R[cur]-cur);
            if(ok1&&ok2)ans+=abs(L[cur]-R[cur]);
            R[L[cur]]=R[cur],L[R[cur]]=L[cur];
        }
    }
    rep(i,1,m)print(ANS[i],'\n');
    fprintf(stderr,"time used=%.10f\n",clock()/1./CLOCKS_PER_SEC);
    return 0;
}

/*
6 2
4 1 6 2 3 5 
1 4
3 6
*/