#include <bits/stdc++.h>

#define jjs(i, s, x) for (int i = (s); i < (x); i++)
#define jjl(i, x) jjs(i, 0, x)
#define ji(x) jjl(i, x)
#define jj(x) jjl(j, x)
#define jk(x) jjl(k, x)
#define jij(a, b) ji(a) jj(b)
#define ever ;;
#define foreach(x, C) for (auto& x : (C))
#define INF ((int) 1e9+10)
#define LINF ((ll) 1e16)
#define pb push_back
#define mp make_pair
#define rint(x) scanf("%d", &(x))
#define rlong(x) scanf("%lld", &(x))
#define nrint(x) int x; rint(x);
#define nrlong(x) long long x; rlong(x);
#define rfloat(x) scanf("%lf", &(x))

const int MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

const int MX = 2010;
ll answer[MX][MX];
int N;
int arr[MX];
int buf[MX];
map<int, int> idxMap;
ll bit[5][MX];

ll read(int b, int p)
{
	p += 5;
	p = min(p, MX - 1);
	ll ans = 0;
	while (p)
	{
		ans += bit[b][p];
		p -= p & -p;
	}
	return ans;
}
void upd(int b, int p, ll v)
{
	p += 5;
	p = max(1, p);
	while (p < MX)
	{
		bit[b][p] += v;
		p += p & -p;
	}
}

ll readLow(int b, int p)
{
	return read(b, p - 1);
}

ll readHigh(int b, int p)
{
	return read(b, INF) - read(b, p);
}

int main()
{
	rint(N);
	nrint(Q);
	ji(N) rint(arr[i]);
	ji(N) buf[i] = arr[i];
	sort(buf, buf + N);
	int idx = 0;
	ji(N)
	{
		if (i == 0 || buf[i] != buf[i-1])
			idxMap[buf[i]] = idx++;
	}
	ji(N) arr[i] = idxMap[arr[i]];
	ji(N)
	{
		memset(bit, 0, sizeof bit);
		ll ans = 0;
		upd(1, arr[i], 1);
		for (int j = i; j < N; j++)
		{
			answer[i][j] = readLow(4, arr[j]);
			upd(4, arr[j], readHigh(3, arr[j]));
			upd(3, arr[j], readLow(2, arr[j]));
			upd(2, arr[j], readHigh(1, arr[j]));
		}
	}
	jk(Q)
	{
		nrint(a); nrint(b);
		printf("%lld\n", answer[a-1][b-1]);
	}
}