/*
 * Author - Abhas Jain
 * Code is inside the solve function
 */
 
#include <bits/stdc++.h>
 
#define F first
#define S second
#define all(c) c.begin(), c.end()
#define endl '\n'
#define pb push_back

typedef long long ll;
typedef long double ld;

using namespace std;
mt19937 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const ld PI = 3.141592653589793;
const ll INF = 9223372036854775807ll;
const ll mod = 1e9 + 7;
const int sqr = 708;

struct node {
	int l, r, i;
};

bool cmp(node a, node b) {
	if (a.l / sqr != b.l / sqr) {
		return a.l / sqr < b.l / sqr;
	}
	return a.r < b.r;
}

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef AJ47
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

void solve() 
{
	int n, q;
	cin >> n >> q;
	vector<int> c(n);
	for (int i = 0; i < n; ++i) {
		cin >> c[i];
	}
	//debug(c);
	vector<node> query(q);
	for (int i = 0; i < q; ++i) {
		cin >> query[i].l >> query[i].r;
		query[i].l--;
		query[i].r--;
		query[i].i = i;
	}
	sort(all(query), cmp);
	vector<int> freq(n + 1, 0);
	vector<int> ans(q);
	int cl = 0, cr = 0, pr = 0;
	for (int i = 0; i < q; ++i) {
		int l = query[i].l, r = query[i].r;
		//debug(l, r, cl, cr);
		while (cl < l) {
			freq[c[cl]]--;
			if (freq[c[cl]] == 0) pr--;
			cl++;
		}
		while (cl > l) {
			freq[c[cl - 1]]++;
			if (freq[c[cl - 1]] == 1) pr++;
			cl--;
		}
		while (cr <= r) {
			freq[c[cr]]++;
			if (freq[c[cr]] == 1) pr++;
			cr++;
		}
		while (cr > r + 1) {
			freq[c[cr - 1]]--;
			if (freq[c[cr - 1]] == 0) pr--;
			cr--;
		}
		ans[query[i].i] = pr;
		//debug(freq);
	}
	
	for (int x : ans) cout << x << " ";
	cout << endl;
}
 
int main( )
{   
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    solve();
    return 0;
}

Measured memory_bytes: 15488