#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fo(i,a,b) for(int i=a;i<=b;++i)

int read () {
	int f = 0; char ch = getchar ();
	for (; ch < '0' || ch > '9'; ch = getchar ());
	for (; ch >= '0' && ch <= '9'; ch = getchar ())
		f = (f<<3) + (f<<1) + ch-'0';
	return f;
}

const int N = 5e5 + 5;

int n, m;
int a[N];
struct nod {
	int ri, l, r;
}q[N];
int u[N], tu;
int d[N], td;
struct Seg {
	int lc, rc;
	int Max;
}t[N<<1];
int tl=0;
ll tr[N];
ll ans[N];

bool cmp (nod A, nod B) {
	if (A.r == B.r)return A.l > B.l;
	return A.r < B.r;
}

void build(int l,int r) {
	int now = ++tl;
	t[tl].lc = t[tl].rc = t[tl].Max = 0;
	if (l<r) {
		int mid=l+r >> 1;
		t[now].lc = tl+1; build(l,mid);
		t[now].rc = tl+1; build(mid+1,r);
	}
	return;
}

void add(int l, int r, int k, int x,int y) {
	if (l==r) {t[k].Max = y;return;}
	int mid = l+r >> 1;
	if (x <= mid) add (l, mid, t[k].lc, x, y);
	else add (mid+1, r, t[k].rc, x, y);
	t[k].Max = max (t[t[k].lc].Max, t[t[k].rc].Max);
	return;
}

int query (int l, int r, int k, int L, int R) {
	if (L > r || l > R)return 0;
	if (l >= L && r <= R)return t[k].Max;
	int mid = l+r >> 1;
	return max (query (l,mid, t[k].lc,L,R), query(mid+1,r,t[k].rc,L,R));
}

#define lowbit(x) ((x)&(-(x)))

void addtr (int x, int y) {
	for (int i = x; i <= n; i += lowbit(i))
		tr[i] += y;
	return;
}

int Calc (int x, int y) {
	if (!x||!y)return 0;
	return abs(x-y);
}

int quetr(int x) {
	int res=0;
	for (int i = x; i >= 1; i -= lowbit(i))
		res += tr[i];
	return res;
}

int main () {
	freopen ("rrads.in", "r", stdin);
	freopen ("rrads.out", "w", stdout);
	scanf ("%d %d", &n, &m);
	fo (i,1,n) a[i] = read ();
	build (1,n);
	fo (i,1,m) {
		q[i].l = read ();
		q[i].r = read ();
		q[i].ri = i;
	}
	sort (q+1, q+1+m, cmp);
	memset (tr, 0, sizeof (tr));
	memset (ans, 0, sizeof (ans));
	memset (u, 0, sizeof (u));
	memset (d, 0, sizeof (d));
	int j = 0;
	fo (i,1,n) {
		tu = td = 0;
		int tmp;
		tmp = query (1, n, 1, a[i]+1, n);
		while (tmp) {
			u[++tu] = tmp;
			tmp = query (1, n, 1, a[i]+1, a[tmp]-1);
		}
		tmp = query (1, n, 1, 1, a[i]-1);
		while (tmp) {
			d[++td] = tmp;
			tmp = query (1, n, 1, a[tmp]+1, a[i]-1);
		}
		int j1 = 0, j2 = 0;
		int lst = 0;
		while (j1 < tu && j2 < td) {
			if (u[j1 + 1] > d[j2 + 1]) {
				++j1;
				int now = -Calc (u[j1-1], d[j2]) + Calc (u[j1], i);
				addtr (n-u[j1]+1, now-lst);
				lst = now;
			} else {
				++j2;
				int now = -Calc (u[j1], d[j2-1]) + Calc (d[j2], i);
				addtr (n-d[j2]+1, now-lst);
				lst = now;
			}
		}
		while (j1 < tu) {
			++j1;
			int now = -Calc (u[j1-1], d[j2]) + Calc (u[j1], i);
			addtr (n-u[j1]+1, now-lst);
			lst = now;
		}
		while (j2 < td) {
			++j2;
			int now = -Calc (u[j1], d[j2-1]) + Calc (d[j2], i);
			addtr (n-d[j2]+1, now-lst);
			lst = now;
		}
		while (j < m && q[j+1].r == i) {
			++j;
			ans[q[j].ri] = quetr (n-q[j].l+1);
		}
		add (1, n, 1, a[i], i);
//		printf ("%d\n", quetr (n));
	}
	fo (i,1,m) printf ("%lld\n", ans[i]);
	return 0;
}

answer.code:1:10: fatal error: bits/stdc++.h: No such file or directory
 #include <bits/stdc++.h>
          ^~~~~~~~~~~~~~~
compilation terminated.