/*
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);
}
LyoKSGFuaXQgQmFuZ2EKKi8KCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGZhc3RfY2luKCkgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSkKCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXIgPGludCwgaW50PiBwaWk7CnR5cGVkZWYgcGFpciA8bGwsIGxsPiBwbGw7Cgpjb25zdCBpbnQgTiA9IDVlNSArIDU7CgppbnQgYVtOXSwgb2NjW05dWzNdLCBhbnNbTl0sIHRyZWVbMypOXTsKcGlpIHRlbXBbTl07CnZlY3RvciA8cGlpPiBxdWVyeVtOXTsKCnZvaWQgdXBkYXRlVHJlZShpbnQgaSwgaW50IGwsIGludCByLCBpbnQgcCwgaW50IHZhbCk7CmludCBxdWVyeVRyZWUoaW50IGksIGludCBsLCBpbnQgciwgaW50IHFsLCBpbnQgcXIpOwoKaW50IG1haW4oKQp7CglpbnQgbiwgcTsKCWNpbiA+PiBuID4+IHE7CgoJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKQoJewoJCWNpbiA+PiB0ZW1wW2ldLmZpcnN0OwoJCXRlbXBbaV0uc2Vjb25kID0gaTsKCX0KCglzb3J0KHRlbXAgKyAxLCB0ZW1wICsgbiArIDEpOwoJaW50IG54dCA9IDE7CglhW3RlbXBbMV0uc2Vjb25kXSA9IDE7Cglmb3IgKGludCBpID0gMjsgaSA8PSBuOyArK2kpCgl7CgkJaWYgKHRlbXBbaV0uZmlyc3QgIT0gdGVtcFtpIC0gMV0uZmlyc3QpCgkJCSsrbnh0OwoKCQlhW3RlbXBbaV0uc2Vjb25kXSA9IG54dDsKCX0KCglmb3IgKGludCBpID0gMTsgaSA8PSBuOyArK2kpCgkJZm9yIChpbnQgaiA9IDA7IGogPCAzOyArK2opCgkJCW9jY1tpXVtqXSA9IC0xOwoKCS8vIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKQoJLy8gCWNvdXQgPDwgYVtpXSA8PCAnICc7CgoJZm9yIChpbnQgaSA9IDE7IGkgPD0gcTsgKytpKQoJewoJCWludCBsLCByOwoJCWNpbiA+PiBsID4+IHI7CgkJcXVlcnlbcl0ucGIoe2wsIGl9KTsKCX0KCglmb3IgKGludCByID0gMTsgciA8PSBuOyArK3IpCgl7CgkJaW50IGN1ciA9IGFbcl07CgkJaWYgKG9jY1tjdXJdWzBdID09IC0xKQoJCQlvY2NbY3VyXVswXSA9IHI7CgoJCWVsc2UgaWYgKG9jY1tjdXJdWzFdID09IC0xKQoJCXsKCQkJb2NjW2N1cl1bMV0gPSBvY2NbY3VyXVswXTsKCQkJb2NjW2N1cl1bMF0gPSByOwoJCQl1cGRhdGVUcmVlKDEsIDEsIG4sIG9jY1tjdXJdWzFdLCAxKTsKCQl9CgoJCWVsc2UgaWYgKG9jY1tjdXJdWzJdID09IC0xKQoJCXsKCQkJZm9yIChpbnQgaSA9IDI7IGkgPj0gMTsgLS1pKQoJCQkJb2NjW2N1cl1baV0gPSBvY2NbY3VyXVtpLTFdOwoKCQkJb2NjW2N1cl1bMF0gPSByOwoJCQl1cGRhdGVUcmVlKDEsIDEsIG4sIG9jY1tjdXJdWzJdLCAtMik7CgkJCXVwZGF0ZVRyZWUoMSwgMSwgbiwgb2NjW2N1cl1bMV0sIDEpOwoJCX0KCgkJZWxzZQoJCXsKCQkJdXBkYXRlVHJlZSgxLCAxLCBuLCBvY2NbY3VyXVsyXSwgMSk7CgkJCWZvciAoaW50IGkgPSAyOyBpID49IDE7IC0taSkKCQkJCW9jY1tjdXJdW2ldID0gb2NjW2N1cl1baS0xXTsKCgkJCW9jY1tjdXJdWzBdID0gcjsKCQkJdXBkYXRlVHJlZSgxLCAxLCBuLCBvY2NbY3VyXVsyXSwgLTIpOwoJCQl1cGRhdGVUcmVlKDEsIDEsIG4sIG9jY1tjdXJdWzFdLCAxKTsKCQl9CgoJCWZvciAoYXV0byAmaSA6IHF1ZXJ5W3JdKQoJCQlhbnNbaS5zZWNvbmRdID0gcXVlcnlUcmVlKDEsIDEsIG4sIGkuZmlyc3QsIHIpOwoJfQoKCWZvciAoaW50IGkgPSAxOyBpIDw9IHE7ICsraSkKCQljb3V0IDw8IGFuc1tpXSA8PCAnXG4nOwp9Cgp2b2lkIHVwZGF0ZVRyZWUoaW50IGksIGludCBsLCBpbnQgciwgaW50IHAsIGludCB2YWwpCnsKCWlmIChwIDwgbCBvciBwID4gcikKCQlyZXR1cm47CgoJdHJlZVtpXSArPSB2YWw7CglpZiAobCA9PSByKQoJCXJldHVybjsKCglpbnQgbWlkID0gKGwgKyByKSAvIDI7Cgl1cGRhdGVUcmVlKDIqaSwgbCwgbWlkLCBwLCB2YWwpOwoJdXBkYXRlVHJlZSgyKmkgKyAxLCBtaWQgKyAxLCByLCBwLCB2YWwpOwp9CgppbnQgcXVlcnlUcmVlKGludCBpLCBpbnQgbCwgaW50IHIsIGludCBxbCwgaW50IHFyKQp7CglpZiAocXIgPCBsIG9yIHFsID4gcikKCQlyZXR1cm4gMDsKCglpZiAocWwgPD0gbCBhbmQgciA8PSBxcikKCQlyZXR1cm4gdHJlZVtpXTsKCglpbnQgbWlkID0gKGwgKyByKSAvIDI7CglyZXR1cm4gcXVlcnlUcmVlKDIqaSwgbCwgbWlkLCBxbCwgcXIpICsgcXVlcnlUcmVlKDIqaSArIDEsIG1pZCArIDEsIHIsIHFsLCBxcik7Cn0=