#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <limits>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <random>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
struct FIO{FIO(){std::cin.tie(0);std::cout.tie(0);std::ios_base::sync_with_stdio(0);std::cout<<std::fixed<<std::setprecision(15);}}fIO;
/*-*/

template <typename T>
std::vector<int> sort_indexes(const std::vector<T> &v) {
	std::vector<int> idx(v.size());
	std::iota(idx.begin(), idx.end(), 0);
	std::sort(idx.begin(), idx.end(), [&v](int i1, int i2) {return v[i1] < v[i2];});
	return idx;
}

template<typename T=lnt>
struct RangeAffineRangeSum
{
	struct M
	{
		T v; int n;
		static M I() { return M(0,1); }
		M(T v, int n=1) : v(v),n(n) {}
		static M f(const M& lhs, const M& rhs) { return M(lhs.v+rhs.v,lhs.n+rhs.n); }
		operator T() const { return v; }
	};

	struct OM
	{
		T a, b; bool alive;
		static OM I() { return OM(); }
		OM() : alive(false) {}
		OM(T a, T b) : a(a),b(b),alive(true) {}
		static M g(const M& m, const OM& om) { if(om.alive) return M(m.v*om.a+T(m.n)*om.b,m.n); else return m; }
		static OM h(const OM& first, const OM& second) {
			if(first.alive&&second.alive) return OM(first.a*second.a, first.b*second.a+second.b);
			return (first.alive)?first:second;
		}
	};
};

template<typename M, typename OM>
struct LazySegmentTree
{
	int n,h;
	std::vector<M> data; std::vector<OM> lazy;
	LazySegmentTree(int N) : n(1),h(0) { while(n<N) n<<=1,h++; data.assign(n<<1,M::I()); lazy.assign(n,OM::I()); }
	M& operator[](int i) { return data[i+n]; } // unsafe. use only with build
	void build() { for(int i=n-1;i>0;i--) data[i]=M::f(data[i<<1],data[i<<1|1]); }
	void apply(int i, const OM& o) { if(i<n) lazy[i]=OM::h(lazy[i],o); data[i]=OM::g(data[i],o); }
	void propagate(int i) { if(lazy[i].alive) { apply(i<<1,lazy[i]); apply(i<<1|1,lazy[i]); lazy[i]=OM::I(); } }
	void thrust(int i) { for(int j=h;j>0;j--) propagate(i>>j); }
	void recalc(int i) { for(;i>1;i>>=1) data[i>>1]=M::f(data[i],data[i^1]); }
	void update(int l, int r, const OM& o) {
		l+=n;r+=n; int l0=l/(l&-l),r0=r/(r&-r); thrust(l0); thrust(r0-1);
		for(;l<r;l>>=1,r>>=1) { if(l&1) apply(l++,o); if(r&1) apply(--r,o); }
		recalc(l0); recalc(r0-1);
	}
	M fold(int l, int r) {
		l+=n;r+=n; int l0=l/(l&-l),r0=r/(r&-r); thrust(l0); thrust(r0-1); recalc(l0); recalc(r0-1);
		M L=M::I(),R=M::I();
		for(;l<r;l>>=1,r>>=1) { if(l&1) L=M::f(L,data[l++]); if(r&1) R=M::f(data[--r],R); }
		return M::f(L,R);
	}
	M get(int i) { return fold(i,i+1); }
};


int main() {
	lnt n,q;
	std::cin >> n >> q;
	std::vector<lnt> c(n);
	rep(i,n) std::cin >> c[i];
	std::vector<std::pair<lnt,lnt> > qu;
	rep(i,q) {
		lnt l,r;
		std::cin >> l >> r;
		qu.emplace_back(l-1,r-1);
	}
	debug("?");
	auto idx = sort_indexes<std::pair<lnt,lnt> >(qu);
	using T=RangeAffineRangeSum<lnt>;
	debug("?");
	LazySegmentTree<T::M,T::OM> seg(n+1);
	std::map<lnt,std::vector<lnt> > map;
	debug("?");
	rep(i,n) {
		map[c[i]].emplace_back(i);
		if(map[c[i]].size()==1) seg.update(i,n+1,T::OM(1,1));
	}
	lnt j=0;
	std::vector<lnt> ans(q);
	rep(i,n) {
		while(j<q&&qu[idx[j]].first==i) {
			ans[idx[j]]=seg.get(qu[idx[j]].second);
			j++;
		}
		// c[i] disappears
		auto ub = std::upper_bound(all(map[c[i]]),i);
		if(ub==map[c[i]].end()) seg.update(i,n+1,T::OM(1,-1));
		else seg.update(i,*ub,T::OM(1,-1));
	}
	debug("?");
	rep(i,q) print(ans[i]);
}


Measured memory_bytes: 104928