/* Priyansh Agarwal*/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<unordered_set>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<map>
#include<chrono>
using namespace std;
using namespace __gnu_pbds;
using namespace std::chrono;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define nline "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define debug(x) cout << #x << " " << x <<endl;
#define set_bits __builtin_popcount
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > pbds;
/*---------------------------------------------------------------------------------------------------------------------------*/
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size 3
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
bool revsort(ll a, ll b) {return a > b;}
void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
ll combination(ll n, ll r, ll m, ll* fact) {ll val1 = fact[n]; ll val2 = mminvprime(fact[r], m); ll val3 = mminvprime(fact[n - r], m); return ((val1 * val2) % m * val3) % m;}
void google(int t) {cout << "Case #" << t << ": ";}
vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
/*--------------------------------------------------------------------------------------------------------------------------*/
int block_size;
bool compare(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
{
int b1 = p1.ff.ff / block_size;
int b2 = p2.ff.ff / block_size;
if (b1 == b2)
return b1 % 2 == 0 ? (p1.ff.ss < p2.ff.ss) : (p1.ff.ss > p2.ff.ss);
return b1 < b2;
}
int main()
{
fastio();
// #ifndef ONLINE_JUDGE
// freopen("Input.txt", "r", stdin);
// freopen("Output.txt", "w", stdout);
// freopen("Error.txt", "w", stderr);
// #endif
auto start1 = high_resolution_clock::now();
int n, q;
cin >> n >> q;
block_size = int(sqrt(n + 0.0) + 1);
int arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
int start = 0;
int end = -1;
vector<pair<pair<int, int>, int>> ans(q);
map<int, int> m1;
for (int i = 0; i < q; i ++)
{
int a, b;
cin >> a >> b;
ans[i] = {{a, b}, i};
}
sort(ans.begin(), ans.end(), compare);
int *ans1 = new int[q];
int count = 0;
for (auto i : ans)
{
pair<pair<int, int>, int> p1 = i;
int right = p1.ff.ss - 1;
int left = p1.ff.ff - 1;
while (start < left)
{
int x = arr[start];
m1[x]--;
if (m1[x] == 0)
count--;
start++;
}
while (start > left)
{
start--;
int x = arr[start];
m1[x]++;
if (m1[x] == 1)
count++;
}
while (end < right)
{
end++;
int x = arr[end];
m1[x]++;
if (m1[x] == 1)
count++;
}
while (end > right)
{
int x = arr[end];
m1[x]--;
if (m1[x] == 0)
count--;
end--;
}
ans1[p1.ss] = count;
}
for (int i = 0; i < q; i++)
cout << ans1[i] << "\n";
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
// #ifndef ONLINE_JUDGE
// cerr << "Time: " << duration.count() / 1000.0 << endl;
// #endif
return 0;
}
LyogUHJpeWFuc2ggQWdhcndhbCovCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgojaW5jbHVkZTxleHQvcGJfZHMvdHJlZV9wb2xpY3kuaHBwPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPHVub3JkZXJlZF9tYXA+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8dW5vcmRlcmVkX3NldD4KI2luY2x1ZGU8c2V0PgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxzdGFjaz4KI2luY2x1ZGU8bWFwPgojaW5jbHVkZTxjaHJvbm8+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwp1c2luZyBuYW1lc3BhY2Ugc3RkOjpjaHJvbm87CiNkZWZpbmUgZmFzdGlvKCkgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7Y2luLnRpZShOVUxMKTtjb3V0LnRpZShOVUxMKQojZGVmaW5lIE1PRCAxMDAwMDAwMDA3CiNkZWZpbmUgTU9EMSA5OTgyNDQzNTMKI2RlZmluZSBubGluZSAiXG4iCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBQSSAzLjE0MTU5MjY1MzU4OTc5MzIzODQ2MgojZGVmaW5lIGRlYnVnKHgpIGNvdXQgPDwgI3ggPDwgIiAiIDw8IHggPDxlbmRsOwojZGVmaW5lIHNldF9iaXRzIF9fYnVpbHRpbl9wb3Bjb3VudAp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxsZDsKdHlwZWRlZiB0cmVlPGludCwgbnVsbF90eXBlLCBsZXNzPGludD4sIHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGUgPiBwYmRzOwovKi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSovCmxsIGdjZChsbCBhLCBsbCBiKSB7aWYgKGIgPiBhKSB7cmV0dXJuIGdjZChiLCBhKTt9IGlmIChiID09IDApIHtyZXR1cm4gYTt9IHJldHVybiBnY2QoYiwgYSAlIGIpO30KbGwgZXhwbyhsbCBhLCBsbCBiLCBsbCBtb2QpIHtsbCByZXMgPSAxOyB3aGlsZSAoYiA+IDApIHtpZiAoYiAmIDEpcmVzID0gKHJlcyAqIGEpICUgbW9kOyBhID0gKGEgKiBhKSAlIG1vZDsgYiA9IGIgPj4gMTt9IHJldHVybiByZXM7fQp2b2lkIGV4dGVuZGdjZChsbCBhLCBsbCBiLCBsbCp2KSB7aWYgKGIgPT0gMCkge3ZbMF0gPSAxOyB2WzFdID0gMDsgdlsyXSA9IGE7IHJldHVybiA7fSBleHRlbmRnY2QoYiwgYSAlIGIsIHYpOyBsbCB4ID0gdlsxXTsgdlsxXSA9IHZbMF0gLSB2WzFdICogKGEgLyBiKTsgdlswXSA9IHg7IHJldHVybjt9IC8vcGFzcyBhbiBhcnJ5IG9mIHNpemUgMwpsbCBtbWludihsbCBhLCBsbCBiKSB7bGwgYXJyWzNdOyBleHRlbmRnY2QoYSwgYiwgYXJyKTsgcmV0dXJuIGFyclswXTt9IC8vZm9yIG5vbiBwcmltZSBiCmxsIG1taW52cHJpbWUobGwgYSwgbGwgYikge3JldHVybiBleHBvKGEsIGIgLSAyLCBiKTt9CmJvb2wgcmV2c29ydChsbCBhLCBsbCBiKSB7cmV0dXJuIGEgPiBiO30Kdm9pZCBzd2FwKGludCAmeCwgaW50ICZ5KSB7aW50IHRlbXAgPSB4OyB4ID0geTsgeSA9IHRlbXA7fQpsbCBjb21iaW5hdGlvbihsbCBuLCBsbCByLCBsbCBtLCBsbCogZmFjdCkge2xsIHZhbDEgPSBmYWN0W25dOyBsbCB2YWwyID0gbW1pbnZwcmltZShmYWN0W3JdLCBtKTsgbGwgdmFsMyA9IG1taW52cHJpbWUoZmFjdFtuIC0gcl0sIG0pOyByZXR1cm4gKCh2YWwxICogdmFsMikgJSBtICogdmFsMykgJSBtO30Kdm9pZCBnb29nbGUoaW50IHQpIHtjb3V0IDw8ICJDYXNlICMiIDw8IHQgPDwgIjogIjt9CnZlY3RvcjxpbnQ+IHNpZXZlKGludCBuKSB7aW50KmFyciA9IG5ldyBpbnRbbiArIDFdKCk7IHZlY3RvcjxpbnQ+IHZlY3Q7IGZvciAoaW50IGkgPSAyOyBpIDw9IG47IGkrKylpZiAoYXJyW2ldID09IDApIHt2ZWN0LnB1c2hfYmFjayhpKTsgZm9yIChpbnQgaiA9IDIgKiBpOyBqIDw9IG47IGogKz0gaSlhcnJbal0gPSAxO30gcmV0dXJuIHZlY3Q7fQovKi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tKi8KaW50IGJsb2NrX3NpemU7CmJvb2wgY29tcGFyZShwYWlyPHBhaXI8aW50LCBpbnQ+LCBpbnQ+IHAxLCBwYWlyPHBhaXI8aW50LCBpbnQ+LCBpbnQ+IHAyKQp7CglpbnQgYjEgPSBwMS5mZi5mZiAvIGJsb2NrX3NpemU7CglpbnQgYjIgPSBwMi5mZi5mZiAvIGJsb2NrX3NpemU7CglpZiAoYjEgPT0gYjIpCgkJcmV0dXJuIGIxICUgMiA9PSAwID8gKHAxLmZmLnNzIDwgcDIuZmYuc3MpIDogKHAxLmZmLnNzID4gcDIuZmYuc3MpOwoJcmV0dXJuIGIxIDwgYjI7Cn0KaW50IG1haW4oKQp7CglmYXN0aW8oKTsKLy8gI2lmbmRlZiBPTkxJTkVfSlVER0UKLy8gCWZyZW9wZW4oIklucHV0LnR4dCIsICJyIiwgc3RkaW4pOwovLyAJZnJlb3BlbigiT3V0cHV0LnR4dCIsICJ3Iiwgc3Rkb3V0KTsKLy8gCWZyZW9wZW4oIkVycm9yLnR4dCIsICJ3Iiwgc3RkZXJyKTsKLy8gI2VuZGlmCglhdXRvIHN0YXJ0MSA9IGhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CglpbnQgbiwgcTsKCWNpbiA+PiBuID4+IHE7CglibG9ja19zaXplID0gaW50KHNxcnQobiArIDAuMCkgKyAxKTsKCWludCBhcnJbbl07Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKCQljaW4gPj4gYXJyW2ldOwoJaW50IHN0YXJ0ID0gMDsKCWludCBlbmQgPSAtMTsKCXZlY3RvcjxwYWlyPHBhaXI8aW50LCBpbnQ+LCBpbnQ+PiBhbnMocSk7CgltYXA8aW50LCBpbnQ+IG0xOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBxOyBpICsrKQoJewoJCWludCBhLCBiOwoJCWNpbiA+PiBhID4+IGI7CgkJYW5zW2ldID0ge3thLCBifSwgaX07Cgl9Cglzb3J0KGFucy5iZWdpbigpLCBhbnMuZW5kKCksIGNvbXBhcmUpOwoJaW50ICphbnMxID0gbmV3IGludFtxXTsKCWludCBjb3VudCA9IDA7Cglmb3IgKGF1dG8gaSA6IGFucykKCXsKCQlwYWlyPHBhaXI8aW50LCBpbnQ+LCBpbnQ+IHAxID0gaTsKCQlpbnQgcmlnaHQgPSBwMS5mZi5zcyAtIDE7CgkJaW50IGxlZnQgPSBwMS5mZi5mZiAtIDE7CgkJd2hpbGUgKHN0YXJ0IDwgbGVmdCkKCQl7CgkJCWludCB4ID0gYXJyW3N0YXJ0XTsKCQkJbTFbeF0tLTsKCQkJaWYgKG0xW3hdID09IDApCgkJCQljb3VudC0tOwoJCQlzdGFydCsrOwoJCX0KCQl3aGlsZSAoc3RhcnQgPiBsZWZ0KQoJCXsKCQkJc3RhcnQtLTsKCQkJaW50IHggPSBhcnJbc3RhcnRdOwoJCQltMVt4XSsrOwoJCQlpZiAobTFbeF0gPT0gMSkKCQkJCWNvdW50Kys7CgkJfQoJCXdoaWxlIChlbmQgPCByaWdodCkKCQl7CgkJCWVuZCsrOwoJCQlpbnQgeCA9IGFycltlbmRdOwoJCQltMVt4XSsrOwoJCQlpZiAobTFbeF0gPT0gMSkKCQkJCWNvdW50Kys7CgkJfQoJCXdoaWxlIChlbmQgPiByaWdodCkKCQl7CgkJCWludCB4ID0gYXJyW2VuZF07CgkJCW0xW3hdLS07CgkJCWlmIChtMVt4XSA9PSAwKQoJCQkJY291bnQtLTsKCQkJZW5kLS07CgkJfQoJCWFuczFbcDEuc3NdID0gY291bnQ7Cgl9Cglmb3IgKGludCBpID0gMDsgaSA8IHE7IGkrKykKCQljb3V0IDw8IGFuczFbaV0gPDwgIlxuIjsKCWF1dG8gc3RvcDEgPSBoaWdoX3Jlc29sdXRpb25fY2xvY2s6Om5vdygpOwoJYXV0byBkdXJhdGlvbiA9IGR1cmF0aW9uX2Nhc3Q8bWljcm9zZWNvbmRzPihzdG9wMSAtIHN0YXJ0MSk7Ci8vICNpZm5kZWYgT05MSU5FX0pVREdFCi8vIAljZXJyIDw8ICJUaW1lOiAiIDw8IGR1cmF0aW9uLmNvdW50KCkgLyAxMDAwLjAgPDwgZW5kbDsKLy8gI2VuZGlmCglyZXR1cm4gMDsKfQ==