/*
Hanit Banga
*/

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false)

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 5e5 + 5;

int a[N], occ[N][3], ans[N], tree[3*N];
pii temp[N];
vector <pii> query[N];

void updateTree(int i, int l, int r, int p, int val);
int queryTree(int i, int l, int r, int ql, int qr);

int main()
{
	int n, q;
	cin >> n >> q;

	for (int i = 1; i <= n; ++i)
	{
		cin >> temp[i].first;
		temp[i].second = i;
	}

	sort(temp + 1, temp + n + 1);
	int nxt = 1;
	a[temp[1].second] = 1;
	for (int i = 2; i <= n; ++i)
	{
		if (temp[i].first != temp[i - 1].first)
			++nxt;

		a[temp[i].second] = nxt;
	}

	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < 3; ++j)
			occ[i][j] = -1;

	// for (int i = 0; i < n; ++i)
	// 	cout << a[i] << ' ';

	for (int i = 1; i <= q; ++i)
	{
		int l, r;
		cin >> l >> r;
		query[r].pb({l, i});
	}

	for (int r = 1; r <= n; ++r)
	{
		int cur = a[r];
		if (occ[cur][0] == -1)
			occ[cur][0] = r;

		else if (occ[cur][1] == -1)
		{
			occ[cur][1] = occ[cur][0];
			occ[cur][0] = r;
			updateTree(1, 1, n, occ[cur][1], 1);
		}

		else if (occ[cur][2] == -1)
		{
			for (int i = 2; i >= 1; --i)
				occ[cur][i] = occ[cur][i-1];

			occ[cur][0] = r;
			updateTree(1, 1, n, occ[cur][2], -2);
			updateTree(1, 1, n, occ[cur][1], 1);
		}

		else
		{
			updateTree(1, 1, n, occ[cur][2], 1);
			for (int i = 2; i >= 1; --i)
				occ[cur][i] = occ[cur][i-1];

			occ[cur][0] = r;
			updateTree(1, 1, n, occ[cur][2], -2);
			updateTree(1, 1, n, occ[cur][1], 1);
		}

		for (auto &i : query[r])
			ans[i.second] = queryTree(1, 1, n, i.first, r);
	}

	for (int i = 1; i <= q; ++i)
		cout << ans[i] << '\n';
}

void updateTree(int i, int l, int r, int p, int val)
{
	if (p < l or p > r)
		return;

	tree[i] += val;
	if (l == r)
		return;

	int mid = (l + r) / 2;
	updateTree(2*i, l, mid, p, val);
	updateTree(2*i + 1, mid + 1, r, p, val);
}

int queryTree(int i, int l, int r, int ql, int qr)
{
	if (qr < l or ql > r)
		return 0;

	if (ql <= l and r <= qr)
		return tree[i];

	int mid = (l + r) / 2;
	return queryTree(2*i, l, mid, ql, qr) + queryTree(2*i + 1, mid + 1, r, ql, qr);
}