#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace  std;
template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rep(n) for (int i = 0; i < n; ++i)
#define ps(x) cout << x << endl;
#define ps_end(x) ps(x); return;
#define eb emplace_back
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>

const int md = 1e9 + 7; //998244353 ;
void addto(int &x, int y) { x = x + y; if (x >= md) x -= md; }
int add(int x, int y) { int z = x + y; return z >= md? z -= md : z;}
void updmin(auto&x, auto y ) { if (y < x) x = y;}
void updmax(auto&x, auto y ) { if (y > x) x = y;}
long long pw(auto x, auto y) {	
	long long s = 1;
	while(y) {
		if (y & 1) s = s * x % md;
		x= 1LL * x * x % md; y /= 2;
	}
	return s;
}


const int maxn = 1e6 + 10;

int T, n, m;
struct SegTree {
	struct {
		int l, r, lazy;
		long long sum; //modify0
		inline void set(int in_lazy = 0) {
			lazy += in_lazy;
			sum += in_lazy * (r - l + 1);
		}  //modify1
		inline int get() {
			return sum;
		}; //modify2
	}tr[maxn * 4];
	inline void pushdown(int x) {
		if (tr[x].lazy != 0) {
			tr[x << 1].lazy += tr[x].lazy;
			tr[x << 1].sum += 1LL * tr[x].lazy * (tr[x << 1].r - tr[x << 1].l + 1);
			tr[x << 1 | 1].lazy += tr[x].lazy;
			tr[x << 1 | 1].sum += 1LL * tr[x].lazy * (tr[x << 1 | 1].r - tr[x << 1 | 1].l + 1);
			tr[x].lazy = 0;
		}
		
	};// modify3
	
	inline void pushup(int x) {
		tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum;	
	}; //modify4
	void build(int x, int l, int r) {
		 tr[x].l = l;
		 tr[x].r = r;
		 if (l == r) {                      
			 return;
		 }
		 int mid = (l + r) / 2;
		 build(x * 2, l, mid);
		 build(x * 2 + 1, mid + 1, r);
		 pushup(x);
	};
	void ins_interval(int x, int l, int r, int w) {
		if (l <= tr[x].l && tr[x].r <= r) {
			tr[x].set(w); //modify
			return;
		}
		pushdown(x);
		if (l <= tr[x << 1].r) ins_interval(x << 1, l, r, w);
		if (r >= tr[x << 1|1].l) ins_interval(x << 1|1, l, r, w);
		pushup(x);		
	};
	
	int query(int x, int l, int r) {
		debug(x, l, r);
		if (l <= tr[x].l && tr[x].r <= r) {
			return tr[x].get();  //modify
		}
		pushdown(x);
		ll s = 0;
		if (l <= tr[x << 1].r) s += query(x << 1, l, r);
		if (r >= tr[x << 1|1].l) s += query(x << 1|1, l, r);
		pushup(x);		
		return s;
	};
};
SegTree seg; 

vector<pair<int, int>> q[maxn];
deque<int> ne[maxn];
void task() {
	int nq;
	cin >> n >> nq;

	vi a(n), ans(nq);
	
	rep(n) {
		cin >> a[i];  
	};
	seg.build(1, 0, n - 1);
	rep(n) {
		if (ne[a[i]].size() == 0) seg.ins_interval(1, i, i, 1);
		ne[a[i]].pb(i);
	};
	debug("finish ins");
	rep(nq) {
		int l, r;
		cin >> l >> r;
		--l; --r;
		q[l].eb(r, i);
	};
	rep(n) {
		if (i) {
			ne[a[i - 1]].pop_front();
			if (ne[a[i - 1]]. size() > 0) 
			 seg.ins_interval(1, ne[a[i - 1]][0], ne[a[i - 1]][0], 1);
		}
		debug(i);
		if (q[i].size() == 0) continue;
		for (auto p : q[i]) {
			ans[p.se] = seg.query(1, i, p.fi);
		}
	};
	rep(nq) ps(ans[i]);
	// you should actually read the stuff at the bottom
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout<<fixed<<setprecision(20);
  T = 1;
  for (int ti = 1; ti <= T; ++ti) {
    task();
  }
  return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* write down
*/


Measured memory_bytes: 739764