#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <set>
#define LL (long long)
using namespace std;

const int N = 5e5 + 100;
int n , m , t;
int a[N];
int fans[N];
struct edge{
    int x , y;
    int seat;
}G[N];
set<pair<int , int> >s;
set<pair<int , int> >::iterator it;
set<pair<int , int> >::iterator it2;
set<pair<int , int> >::iterator it3;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            b=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        a=(a<<3)+(a<<1)+c-'0';
        c=getchar();
    }
    return a*b;
}

bool compare(edge s1 , edge s2) {
    if(s1.x / t == s2.x / t) {
        if((s1.x / t) & 1) return s1.y < s2.y;
            else return s1.y > s2.y;
    }
    return s1.x / t < s2.x / t;
}

int main() {
    n = read() , m = read();
    t = sqrt(n);
    for(int i=1;i<=n;i++)
        a[i] = read();
    for(int i=1;i<=m;i++) {
        G[i].x = read();
        G[i].y = read();
        G[i].seat = i;
    }
    sort(G + 1 , G + 1 + m , compare);
    int l = 1 , r = 0;
    long long ans = 0;
    for(int i=1;i<=m;i++) {
        while(r < G[i].y) {
            r ++;
            s.insert(make_pair(a[r] , r));
            it = s.lower_bound(make_pair(a[r] , 0));
            it3 = it2 = it;
            it ++;
            it2 --;
            if(it != s.end() && it3 != s.begin()) ans -= LL(abs(it->second - it2->second));
            if(it != s.end()) ans += LL(abs(it->second - it3->second));
            if(it3 != s.begin()) ans += LL(abs(it3->second - it2->second));
        }
        while(l > G[i].x) {
            l --;
            s.insert(make_pair(a[l] , l));
            it = s.lower_bound(make_pair(a[l] , 0));
            it3 = it2 = it;
            it ++;
            it2 --;
            if(it != s.end() && it3 != s.begin()) ans -= LL(abs(it->second - it2->second));
            if(it != s.end()) ans += LL(abs(it->second - it3->second));
            if(it3 != s.begin()) ans += LL(abs(it3->second - it2->second));
        }
        while(r > G[i].y) {
            it = s.lower_bound(make_pair(a[r] , 0));
            it3 = it2 = it;
            it ++;
            it2 --;
            if(it != s.end() && it3 != s.begin()) ans += LL(abs(it->second - it2->second));
            if(it != s.end()) ans -= LL(abs(it->second - it3->second));
            if(it3 != s.begin()) ans -= LL(abs(it3->second - it2->second));
            s.erase(it3);
            r --;
        }
        while(l < G[i].x) {
            it = s.lower_bound(make_pair(a[l] , 0));
            it3 = it2 = it;
            it ++;
            it2 --;
            if(it != s.end() && it3 != s.begin()) ans += LL(abs(it->second - it2->second));
            if(it != s.end()) ans -= LL(abs(it->second - it3->second));
            if(it3 != s.begin()) ans -= LL(abs(it3->second - it2->second));
            s.erase(it3);
            l ++;
        }
        fans[G[i].seat] = ans;
    }
    for(int i=1;i<=m;i++)
        printf("%lld\n" , fans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}