#17 TLE

代码是大常熟答辩。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctype.h>
#include <cmath>

char ST;
//#define int long long
#define ll long long
int read()
{
	int x = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(;  isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define gline debug("now is #%d\n", __LINE__)
#define pii std::pair <int, int>
#define mkp std::make_pair

void ckmax(int &x, int y) { x = x > y ? x : y; }
void ckmin(int &x, int y) { x = x < y ? x : y; }
//#define mod 998244353
//#define mod 1000000007
//void plus_(int &x, int y) { x = (x + y) % mod; }
//void mul_(int &x, int y) { x = 1ll * x * y % mod; }
//int ksm(int a, int b)
//{
//	int res = 1;
//	for(; b; b >>= 1, mul_(a, a))
//		if(b & 1)
//			mul_(res, a);
//	return res;
//}

#define N 500010

int n, m;
int a[N];
struct Query
{
	int l, r, id;
}q[N];
int len, belong[N], L[N], id[N];
bool vis[N];
int pre[N], suc[N];
ll ans[N];

struct node
{
	int id, pre, suc;
}sta[N];
int top;
bool apr[N];

inline int aBs(int x) { return x > 0 ? x : -x; }

char ED;
signed main()
{
	n = read(), m = read();
	for(int i = 1; i <= n; i++) id[a[i] = read()] = i;
	for(int i = 1; i <= m; i++) q[q[i].id = i].l = read(), q[i].r = read();
	len = n / sqrt(m);
	for(int i = 1; i <= n; i++)
		belong[i] = (i - 1) / len + 1;
	for(int i = 1; i <= belong[n]; i++)
		L[i] = (i - 1) * len + 1;
	std::sort(q + 1, q + 1 + m, [&](Query A, Query B) -> bool
	{ return belong[A.l] != belong[B.l] ? belong[A.l] < belong[B.l] : A.r > B.r; });
	int l = 1, r = n, las = 0;
	ll now = 0;
	int tmp = 0;
	for(int i = 1; i <= m; i++)
	{
		int ql = q[i].l, qr = q[i].r;
		if(belong[ql] != las)
		{
			las = belong[ql];
			now = 0;
			r = n;
			for(int i = 1; i <= n; i++) pre[i] = suc[i] = vis[i] = 0;
			for(int i = L[las]; i <= n; i++) vis[a[i]] = 1;
			int bg = 1, ed = n;
			while(!vis[bg]) bg++;
			while(!vis[ed]) ed--;
			for(int i = bg, nx; i != ed; i = nx)
			{
				for(nx = i + 1; !vis[nx]; nx++);
				suc[i] = nx;
				pre[nx] = i;
				now += aBs(id[i] - id[nx]);
			}
		}
		tmp = 0;
		while(qr < r)
		{
			int t = a[r--];
			vis[t] = 0;
			if(pre[t]) tmp -= aBs(id[t] - id[pre[t]]), suc[pre[t]] = suc[t];
			if(suc[t]) tmp -= aBs(id[t] - id[suc[t]]), pre[suc[t]] = pre[t];
			if(pre[t] && suc[t]) tmp += aBs(id[pre[t]] - id[suc[t]]);
			if(tmp >= 500000000 || tmp <= -500000000)
				now += tmp, tmp = 0;
		}
		now += tmp, tmp = 0;
		ll now_ = now;
		l = L[las];
		while(l < ql)
		{
			int t = a[l++];
			vis[t] = 0;
			if(pre[t]) tmp -= aBs(id[t] - id[pre[t]]), sta[++top] = (node){pre[t], pre[pre[t]], suc[pre[t]]}, suc[pre[t]] = suc[t];
			if(suc[t]) tmp -= aBs(id[t] - id[suc[t]]), sta[++top] = (node){suc[t], pre[suc[t]], suc[suc[t]]}, pre[suc[t]] = pre[t];
			if(pre[t] && suc[t]) tmp += aBs(id[pre[t]] - id[suc[t]]);
			if(tmp >= 500000000 || tmp <= -500000000)
				now += tmp, tmp = 0;
		}
		now += tmp, tmp = 0;
		ans[q[i].id] = now;
		now = now_;
		while(top)
		{
			int t = sta[top].id;
			pre[t] = sta[top].pre;
			suc[t] = sta[top].suc;
			top--;
		}
	}
	for(int i = 1; i <= m; i++)
		printf("%lld\n", ans[i]);
	return 0;
}