#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ULL;
using LL = long long;

mt19937_64 rd(time(0));
constexpr int N = 5e5 + 5, mod = 998244353;
constexpr double eps = 1e-8;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define fi first
#define se second
// #define int long long
#define lowbit(x) (x & (-x))
#define PII pair<int, int>
#define mid ((l + r) >> 1)

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int abs(int x) {return x > 0 ? x : -x;}
int ksm(int a, int b){
    a %= mod;
    int res = 1;
    while(b){
        if(b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int n, m;
int a[N];
int q, id[N];
struct Node{
    int l, r, id;
};
Node Q[N];
int nxt[N], pre[N], B;
int block[N];
bool cmp(Node a, Node b){
    if(block[a.l] != block[b.l])return a.l < b.l;
    else return a.r > b.r;
}
stack<tuple<int, int, int>>stkL, stkR;
LL ans[N], res, num;

void rollL(){
    auto [prex, x, nxtx] = stkL.top();stkL.pop();
    if(prex != 0)res += abs(prex - x);
    if(nxtx != n + 1)res += abs(nxtx - x);
    if(prex != 0 && nxtx != n + 1)res -= abs(prex - nxtx);
    pre[x] = prex;
    nxt[prex] = x;
    pre[nxtx] = x;
    nxt[x] = nxtx;
}

void rollR(){
    auto [prex, x, nxtx] = stkR.top();stkR.pop();
    if(prex != 0)res += abs(prex - x);
    if(nxtx != n + 1)res += abs(nxtx - x);
    if(prex != 0 && nxtx != n + 1)res -= abs(prex - nxtx);
    pre[x] = prex;
    nxt[prex] = x;
    pre[nxtx] = x;
    nxt[x] = nxtx;
}

void del(int x){
    int prex = pre[x];
    int nxtx = nxt[x];
    if(nxtx != n + 1)res -= abs(nxtx - x);
    if(prex != 0)res -= abs(prex - x);
    if(prex != 0 && nxtx != n + 1)res += abs(prex - nxtx);
    pre[nxtx] = prex;
    nxt[prex] = nxtx;
}

void delR(int x){
    int prex = pre[x];
    int nxtx = nxt[x];
    stkR.emplace(prex, x, nxtx);
    if(nxtx != n + 1)res -= abs(nxtx - x);
    if(prex != 0)res -= abs(prex - x);
    if(prex != 0 && nxtx != n + 1)res += abs(prex - nxtx);
    pre[nxtx] = prex;
    nxt[prex] = nxtx;
}

void delL(int x){
    int prex = pre[x];
    int nxtx = nxt[x];
    stkL.emplace(prex, x, nxtx);
    if(nxtx != n + 1)res -= abs(nxtx - x);
    if(prex != 0)res -= abs(prex - x);
    if(prex != 0 && nxtx != n + 1)res += abs(prex - nxtx);
    pre[nxtx] = prex;
    nxt[prex] = nxtx;
}

void Sakuya()
{
    cin >> n >> q;    
    B = sqrt(n);
    for(int i = 1; i <= n; ++ i)cin >> a[i], block[i] = (i - 1) / B + 1;
    num = block[n];
    for(int i = 0; i <= n + 1; ++ i)id[i] = i;
    sort(id + 1, id + 1 + n, [&](int x, int y){return a[x] < a[y];});

    // for(int i = 1; i <= n; ++ i)cout << id[i] << " ";
    // cout << "\n";

    for(int i = 1; i <= n; ++ i)pre[id[i]] = id[i - 1], nxt[id[i]] = id[i + 1];
    nxt[0] = id[1], pre[n + 1] = id[n];

    for(int i = 1; i <= n - 1; ++ i)res += abs(id[i + 1] - id[i]);

    for(int i = 1; i <= q; ++ i){
        cin >> Q[i].l >> Q[i].r;
        Q[i].id = i;
    }

    sort(Q + 1, Q + 1 + q, cmp);
    int pos = 1, L = 1;
    for(int i = 1; i <= num; ++ i){
        int Lnow = (i - 1) * B + 1, R = n;
        while(L < Lnow)del(L ++);
        for(; block[Q[pos].l] == i; pos += 1){
            while(Q[pos].r < R)delR(R --);
            while(Q[pos].l > L)delL(L ++);
            ans[Q[pos].id] = res;
            while(stkL.size()){
                rollL();
                L -= 1;
            }
        }
        while(stkR.size())rollR();
    }

    for(int i = 1; i <= q; ++ i)cout << ans[i] << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // int T;
    // for (cin >> T; T -- ; )
        Sakuya();

}