#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
#define int long long

namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a signed integer
	template <class I>
	inline void read (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	// print a signed integer
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: putc;
using io :: print;
using io :: read;

int N, M;
int A[MAXN], C[MAXN], Prer[MAXN], Prel[MAXN], qwq[MAXN], Belong[MAXN], Size;
int Sum1[320], Sum2[320][320], Ans[MAXN];
int Left[320], Right[320];
vector<tuple<int, int, int, int, int> > V[MAXN];

int lb(int x) {
	return x & -x;
}

void Add(int x) {
	while (x <= N) {
		C[x] += 1;
		x += lb(x);
	}
}

int Query(int x) {
	int res = 0;
	while (x) {
		res += C[x];
		x -= lb(x);
	}
	return res;
}

struct _ {
	int l, r, id, Ans;
	bool operator < (const _ &x) const {
		return Belong[l] == Belong[x.l] ? r < x.r : l < x.l;
	}
} Ask[MAXN];

void UpDate(int x) {
	for (int i = x - Left[Belong[x]], *k = Sum2[Belong[x]]; i < Size; i++) ++k[i];
	for (int i = Belong[x]; i <= Belong[N]; i++) ++Sum1[i];
}

int GetSum(int x) {
	return Sum1[Belong[x] - 1] + Sum2[Belong[x]][x - Left[Belong[x]]];
}

signed main () {
	read(N);
	read(M);
	Size = sqrt(N);
	for (int i = 1; i <= N; i++) {
		read(A[i]);
		qwq[i] = A[i];
		Belong[i] = (i - 1) / Size + 1;
	}
	
	sort(qwq + 1, qwq + 1 + N);
	
	
	for (int i = 1; i <= N; i++) {
		A[i] = lower_bound(qwq + 1, qwq + 1 + N, A[i]) - qwq;
	}
	
	for (int i = 1; i <= M; i++) {
		read(Ask[i].l);
		read(Ask[i].r);
		Ask[i].id = i;
	}
	sort(Ask + 1, Ask + 1 + M);

	for (int i = 1; i <= Belong[N]; i++) {
		Left[i] = Right[i - 1] + 1;
		Right[i] = Size * i;
	} 
	Right[Belong[N]] = N;
	for (int i = 1; i <= N; i++) {
		Prer[i] = Query(N) - Query(A[i]);
		Prel[i] = Query(A[i] - 1);
		Add(A[i]);
	}
	
	for (int i = 1, l = 1, r = 0; i <= M; i++) {
		if (l > Ask[i].l) V[r].emplace_back(Ask[i].l, l - 1, 1, i, 1);
		while (l > Ask[i].l) Ask[i].Ans -= Prel[--l];
		if (r < Ask[i].r) V[l - 1].emplace_back(r + 1, Ask[i].r, 0, i, -1);
		while (r < Ask[i].r) Ask[i].Ans += Prer[++r];
		if (l < Ask[i].l) V[r].emplace_back(l , Ask[i].l - 1, 1, i, -1);
		while (l < Ask[i].l) Ask[i].Ans += Prel[l++];
		if (r > Ask[i].r) V[l - 1].emplace_back(Ask[i].r + 1, r, 0, i, 1);
		while (r > Ask[i].r) Ask[i].Ans -= Prer[r--];
	}
	
	for (int p = 1; p <= N; p++) {
		static int l, r, cmp, id, op;
		UpDate(A[p]); 
		for (const auto &x : V[p]) {
			tie(l, r, cmp, id, op) = x;
			for (int i = l; i <= r; i++) {
				if (cmp == 1) Ask[id].Ans += op * GetSum(A[i] - 1);
				else Ask[id].Ans += op * (GetSum(N) - GetSum(A[i]));
			}
		}
	}

	for(int i = 1; i <= M; i++) Ask[i].Ans += Ask[i - 1].Ans;
	for(int i = 1; i <= M; i++) Ans[Ask[i].id] = Ask[i].Ans;
	for(int i = 1; i <= M; i++) {
		print(Ans[i]);
		putc('\n');
	}
	return 0;
}

300+ms