// Problem: P11367 [Ynoi2024] 魔法少女网站第二部
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11367
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

namespace IO {
	const int maxn = 1 << 20;
	
    char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

	inline char gc() {
		return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
	}

	template<typename T = int>
	inline T read() {
		char c = gc();
		T x = 0;
		bool f = 0;
		while (c < '0' || c > '9') {
			f |= (c == '-');
			c = gc();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c ^ 48);
			c = gc();
		}
		return f ? ~(x - 1) : x;
	}

	inline void flush() {
		fwrite(obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	
	struct Flusher {
		~Flusher() {
			flush();
		}
	} AutoFlush;

	inline void pc(char ch) {
		if (oS == obuf + maxn) {
			flush();
		}
		*oS++ = ch;
	}

	template<typename T>
	inline void write(T x) {
		static char stk[64], *tp = stk;
		if (x < 0) {
			x = ~(x - 1);
			pc('-');
		}
		do {
			*tp++ = x % 10;
			x /= 10;
		} while (x);
		while (tp != stk) {
			pc((*--tp) | 48);
		}
	}
	
	template<typename T>
	inline void writesp(T x) {
		write(x);
		pc(' ');
	}
	
	template<typename T>
	inline void writeln(T x) {
		write(x);
		pc('\n');
	}
}

using IO::read;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 2000100;
const int inf = 0x3f3f3f3f;

int n, m, a[maxn], b[maxn], d[maxn], f[maxn], g[maxn], pre[maxn], suf[maxn];
pii p[maxn], q[maxn], h[maxn];

struct node {
	int l, r;
} c[maxn];

ll ans[maxn];

struct List {
	int hd[maxn * 3], len, val[maxn << 1], nxt[maxn << 1];
	
	inline void add(int x, int y) {
		val[++len] = y;
		nxt[len] = hd[x];
		hd[x] = len;
	}
} G, T;

namespace BIT {
	int n;
	ll c[maxn];
	
	inline void init(int _n) {
		n = _n;
		for (int i = 0; i <= n; ++i) {
			c[i] = 0;
		}
	}
	
	inline void update(int x, int d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline ll query(int x) {
		ll res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
	
	inline ll query(int l, int r) {
		return query(r) - query(l - 1);
	}
	
	inline void clear(int x) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] = 0;
		}
	}
}

int fa[maxn];

inline int find(int x) {
	while (fa[x] != x) {
		x = fa[x] = fa[fa[x]];
	}
	return x;
}

void update(int rt, int l, int r, int ql, int qr, int i) {
	int mid = (l + r) >> 1;
	if (qr <= mid) {
		update(rt << 1, l, mid, ql, qr, i);
	} else if (ql > mid) {
		update(rt << 1 | 1, mid + 1, r, ql, qr, i);
	} else {
		T.add(rt, i);
	}
}

void dfs(int rt, int l, int r) {
	if (l == r) {
		return;
	}
	int mid = (l + r) >> 1;
	dfs(rt << 1, l, mid);
	dfs(rt << 1 | 1, mid + 1, r);
	inplace_merge(p + l, p + mid + 1, p + r + 1);
	G.len = 0;
	for (int i = l; i <= r; ++i) {
		G.hd[i] = 0;
	}
	for (int i = l; i <= r; ++i) {
		d[p[i].scd] = i - l + 1;
	}
	for (int i = l; i <= r; ++i) {
		b[d[i]] = i;
	}
	for (int i = T.hd[rt]; i; i = T.nxt[i]) {
		int j = T.val[i];
		G.add(c[j].l, j);
		G.add(c[j].r, j);
	}
	ll s = 0;
	int mn = inf, mx = 0, tot = r - l + 1;
	int lst0 = 0, lst1 = 0, mx0 = 0, mn1 = inf;
	for (int i = 1; i <= tot; ++i) {
		if (b[i] <= mid) {
			if (lst0) {
				f[b[lst0]] = mn1;
			}
			mn1 = inf;
			lst0 = i;
			mx0 = max(mx0, b[i]);
		} else {
			if (lst1) {
				g[b[lst1]] = mx0;
			}
			mx0 = 0;
			lst1 = i;
			mn1 = min(mn1, b[i]);
		}
	}
	f[b[lst0]] = inf;
	g[b[lst1]] = 0;
	for (int i = 1; i <= tot; ++i) {
		fa[i] = (b[i] <= mid ? i : i - 1);
	}
	fa[0] = 0;
	for (int i = l; i <= mid; ++i) {
		int t = find(d[i] - 1);
		fa[d[i]] = q[i].fst = t;
		h[i].scd = f[i];
		if (t) {
			t = b[t];
			h[i].fst = f[t];
			f[t] = min(f[t], f[i]);
		}
	}
	for (int i = 1; i <= tot; ++i) {
		fa[i] = (b[i] <= mid ? i : i + 1);
	}
	fa[tot + 1] = tot + 1;
	for (int i = l; i <= mid; ++i) {
		fa[d[i]] = q[i].scd = find(d[i] + 1);
	}
	pre[0] = suf[tot + 1] = inf;
	for (int i = 1; i <= tot; ++i) {
		pre[i] = min(pre[i - 1], b[i] > mid ? b[i] : inf);
	}
	for (int i = tot; i; --i) {
		suf[i] = min(suf[i + 1], b[i] > mid ? b[i] : inf);
	}
	BIT::init(r - mid);
	for (int i = mid; i >= l; --i) {
		mn = min(mn, d[i]);
		mx = max(mx, d[i]);
		int j = q[i].fst, k = q[i].scd, p = inf;
		if (j) {
			s += abs(i - b[j]);
			int t = h[i].fst;
			p = min(p, t);
			if (t <= r) {
				BIT::update(t - mid, (mid - max(i, b[j])) * 2);
			}
		}
		if (k <= tot) {
			s += abs(i - b[k]);
			int t = h[i].scd;
			p = min(p, t);
			if (t <= r) {
				BIT::update(t - mid, (mid - max(i, b[k])) * 2);
			}
		}
		if (j && k <= tot) {
			s -= abs(b[j] - b[k]);
			if (p <= r) {
				BIT::update(p - mid, -(mid - max(b[j], b[k])) * 2);
			}
		}
		for (int _ = G.hd[i]; _; _ = G.nxt[_]) {
			int j = G.val[_];
			ans[j] += s + BIT::query(c[j].r - mid);
			if (suf[mx + 1] <= c[j].r) {
				ans[j] += mid - b[mx];
			}
			if (pre[mn - 1] <= c[j].r) {
				ans[j] += mid - b[mn];
			}
		}
	}
	s = mx = 0;
	mn = inf;
	for (int i = 1; i <= tot; ++i) {
		fa[i] = (b[i] > mid ? i : i - 1);
	}
	fa[0] = 0;
	for (int i = r; i > mid; --i) {
		int t = find(d[i] - 1);
		fa[d[i]] = q[i].fst = t;
		h[i].scd = g[i];
		if (t) {
			t = b[t];
			h[i].fst = g[t];
			g[t] = max(g[t], g[i]);
		}
	}
	for (int i = 1; i <= tot; ++i) {
		fa[i] = (b[i] > mid ? i : i + 1);
	}
	fa[tot + 1] = tot + 1;
	for (int i = r; i > mid; --i) {
		fa[d[i]] = q[i].scd = find(d[i] + 1);
	}
	pre[0] = suf[tot + 1] = 0;
	for (int i = 1; i <= tot; ++i) {
		pre[i] = max(pre[i - 1], b[i] <= mid ? b[i] : 0);
	}
	for (int i = tot; i; --i) {
		suf[i] = max(suf[i + 1], b[i] <= mid ? b[i] : 0);
	}
	BIT::init(mid - l + 1);
	for (int i = mid + 1; i <= r; ++i) {
		mn = min(mn, d[i]);
		mx = max(mx, d[i]);
		int j = q[i].fst, k = q[i].scd, p = 0;
		if (j) {
			s += abs(i - b[j]);
			int t = h[i].fst;
			p = max(p, t);
			if (t >= l) {
				BIT::update(t - l + 1, (min(i, b[j]) - mid) * 2);
			}
		}
		if (k <= tot) {
			s += abs(i - b[k]);
			int t = h[i].scd;
			p = max(p, t);
			if (t >= l) {
				BIT::update(t - l + 1, (min(i, b[k]) - mid) * 2);
			}
		}
		if (j && k <= tot) {
			s -= abs(b[j] - b[k]);
			if (p >= l) {
				BIT::update(p - l + 1, -(min(b[j], b[k]) - mid) * 2);
			}
		}
		for (int _ = G.hd[i]; _; _ = G.nxt[_]) {
			int j = G.val[_];
			ans[j] += s + BIT::query(c[j].l - l + 1, mid - l + 1);
			if (suf[mx + 1] >= c[j].l) {
				ans[j] += b[mx] - mid;
			}
			if (pre[mn - 1] >= c[j].l) {
				ans[j] += b[mn] - mid;
			}
		}
	}
}

void solve() {
	mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
	n = m = 1000000;
	for (int i = 1; i <= n; ++i) {
		a[i] = i;
	}
	shuffle(a + 1, a + n + 1, rnd);
	for (int i = 1; i <= n; ++i) {
		p[i] = pii(a[i], i);
	}
	for (int i = 1; i <= m; ++i) {
		c[i].l = rnd() % n + 1;
		c[i].r = rnd() % n + 1;
		if (c[i].l > c[i].r) {
			swap(c[i].l, c[i].r);
		}
		if (c[i].l != c[i].r) {
			update(1, 1, n, c[i].l, c[i].r, i);
		}
	}
	dfs(1, 1, n);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}