// Problem: P11365 [Ynoi2024] 新本格魔法少女りすか
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11365
// Memory Limit: 128 MB
// Time Limit: 15000 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 = 500100;
const int B = 400;

int n, m, a[maxn], bel[maxn], L[maxn], R[maxn], b[maxn], c[maxn];
ll ans[maxn];
vector<pii> qq[maxn];

namespace BIT {
	int c[maxn];
	ull b[maxn];
	
	inline void update(int x, int d) {
		b[x >> 6] |= (1ULL << (x & 63));
		for (int i = (x >> 6) + 1; i <= (n >> 6) + 1; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline int query(int x) {
		int res = __builtin_popcountll(b[x >> 6] << (63 - (x & 63)));
		for (int i = (x >> 6); i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
	
	inline void clear(int x) {
		b[x >> 6] = 0;
		for (int i = (x >> 6) + 1; i <= (n >> 6) + 1; i += (i & (-i))) {
			c[i] = 0;
		}
	}
}

void solve() {
	n = read();
	m = read();
	for (int i = 1; i <= n; ++i) {
		a[i] = read();
		bel[i] = (i - 1) / B + 1;
		if (!L[bel[i]]) {
			L[bel[i]] = i;
		}
		R[bel[i]] = i;
	}
	for (int i = 1, k, l, r; i <= m; ++i) {
		k = read();
		while (k--) {
			l = read();
			r = read();
			qq[i].pb(l, r);
			if (bel[l] == bel[r]) {
				for (int j = l; j <= r; ++j) {
					ans[i] += BIT::query(a[j]);
				}
				for (int j = l; j <= r; ++j) {
					BIT::update(a[j], 1);
				}
			} else {
				for (int j = l; j <= R[bel[l]]; ++j) {
					ans[i] += BIT::query(a[j]);
				}
				for (int j = L[bel[r]]; j <= r; ++j) {
					ans[i] += BIT::query(a[j]);
				}
				for (int j = l; j <= R[bel[l]]; ++j) {
					BIT::update(a[j], 1);
				}
				for (int j = L[bel[r]]; j <= r; ++j) {
					BIT::update(a[j], 1);
				}
			}
		}
		for (pii p : qq[i]) {
			int l = p.fst, r = p.scd;
			if (bel[l] == bel[r]) {
				for (int j = l; j <= r; ++j) {
					BIT::clear(a[j]);
				}
			} else {
				for (int j = l; j <= R[bel[l]]; ++j) {
					BIT::clear(a[j]);
				}
				for (int j = L[bel[r]]; j <= r; ++j) {
					BIT::clear(a[j]);
				}
			}
		}
	}
	for (int k = 1; k <= bel[n]; ++k) {
		mems(b, 0);
		for (int i = L[k]; i <= R[k]; ++i) {
			++b[a[i]];
		}
		for (int i = 1; i <= n; ++i) {
			b[i] += b[i - 1];
		}
		for (int i = 1; i <= n; ++i) {
			if (i < L[k]) {
				c[i] = c[i - 1] + R[k] - L[k] + 1 - b[a[i]];
			} else if (i <= R[k]) {
				c[i] = c[i - 1];
			} else {
				c[i] = c[i - 1] + b[a[i] - 1];
			}
		}
		for (int i = 1; i <= m; ++i) {
			bool fl = 0;
			ll s = 0;
			for (pii p : qq[i]) {
				int l = p.fst, r = p.scd;
				int bl = bel[l] + 1, br = bel[r] - 1;
				if (bl <= k && k <= br) {
					fl = 1;
				} else if (r < L[k]) {
					s += c[r] - c[l - 1];
				} else if (l > R[k]) {
					if (!fl) {
						break;
					}
					if (bel[l] == bel[r]) {
						s += c[r] - c[l - 1];
					} else {
						s += c[R[bel[l]]] - c[l - 1] + c[r] - c[L[bel[r]] - 1];
					}
				}
			}
			if (fl) {
				ans[i] += s;
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		writeln(ans[i]);
	}
}

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