/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author rchalamala
 */

/*
ID: rchalam1
LANG: C++14
TASK:
*/
// For train.usaco.org, fill the template above.

// Competitive Coding Template

// GCC OPTIMIAZTION FLAGS
#ifndef LOCAL
#include <x86intrin.h>
#pragma GCC optimize("fast-math,no-stack-protector,Ofast,omit-frame-pointer,unroll-loops,inline")
#pragma GCC option("arch=native,no-zero-upper,tune=native")
#pragma GCC target("abm,avx,avx2,bmi2,fma,mmx,popcnt,sse,sse2,sse3,sse4,ssse3")
#endif

#ifndef GENERAL_HPP
#define GENERAL_HPP

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#include <forward_list>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <mutex>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <string>
#include <thread>
#include <tuple>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>

using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<typename T> using ordered_set = __gnu_pbds::tree<T,
														  __gnu_pbds::null_type,
														  std::less<T>,
														  __gnu_pbds::rb_tree_tag,
														  __gnu_pbds::tree_order_statistics_node_update>;

using ui = unsigned int;
using ul = unsigned long long;
using ll = long long;
using ld = long double;
using cd = std::complex<long double>;

using pui = std::pair<unsigned int, unsigned int>;
using pii = std::pair<int, int>;
using pul = std::pair<unsigned long long, unsigned long long>;
using pll = std::pair<long long, long long>;
using pld = std::pair<long double, long double>;
using pcd = std::pair<std::complex<long double>, std::complex<long double>>;

using vui = std::vector<unsigned int>;
using vii = std::vector<int>;
using vul = std::vector<unsigned long long>;
using vll = std::vector<long long>;
using vld = std::vector<long double>;
using vcd = std::vector<std::complex<long double>>;

using vpui = std::vector<std::pair<unsigned int, unsigned int>>;
using vpii = std::vector<std::pair<int, int>>;
using vpul = std::vector<std::pair<unsigned long long, unsigned long long>>;
using vpll = std::vector<std::pair<long long, long long>>;
using vpld = std::vector<std::pair<long double, long double>>;
using vpcd = std::vector<std::pair<std::complex<long double>, std::complex<long double>>>;

#define FOR(i, a, b) for (auto (i) = (a); (i) < (b); ++(i))
#define F0R(i, a) FOR((i), 0, (a))
#define ROF(i, a, b) for (auto (i) = (a); (i) >= (b); --(i))
#define R0F(i, a) ROF((i), (a), 0)
#define ITR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define FSRT(set) std::sort((set).begin(),(set).end())
#define RSRT(set) std::sort((set).rbegin(),(set).rend())
#define CSRT(set, function) std::sort((set).begin(),(set).end(), (function))
#define UNIQUE(set) std::sort((set).begin(), (set).end()), (set).erase(std::unique((set).begin(), (set.end())), (a).end())

#define ALL(set) (set).begin(), (set).end()
#define RALL(set) (set).rbegin(), (set).rend()

#define mp std::make_pair
#define mt std::make_tuple
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound

#endif
#ifndef IO_HPP
#define IO_HPP












// https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/CppIO.h
namespace std
{

	std::string to_string(const char& element)
	{
		return std::string(1, element);
	}

	std::string to_string(const char* element)
	{
		return std::string(element);
	}

	std::string to_string(const std::string& element)
	{
		return element;
	}

	std::string to_string(const bool& element)
	{
#ifdef LOCAL
		return element ? "true" : "false";
#else
		return std::string{ static_cast<char>('0' + element) };
#endif
	}

	template<typename T>
	std::string to_string(const std::complex<T>& element)
	{
		std::stringstream convert;
		convert << element;
		return convert.str();
	}

	std::string to_string(const std::vector<bool>& elements)
	{
		std::string convert = "{";
		for (const auto& element : elements) convert += static_cast<char>('0' + element);
		return convert + "}";
	}

	template<std::size_t Size>
	std::string to_string(const std::bitset<Size>& elements)
	{
		std::string convert;
		for (auto i = 0; i < Size; ++i) convert += static_cast<char>('0' + elements[i]);
		return convert;
	}

	template<typename T1, typename T2>
	std::string to_string(std::pair<T1, T2> element)
	{
#ifdef LOCAL
		return "(" + std::to_string(element.first) + ", " + std::to_string(element.second) + ")";
#else
		return std::to_string(element.ff) + " " + std::to_string(element.ss);
#endif
	}

	template<typename T>
	std::string to_string(const T& elements)
	{
		std::string convert;
		bool first = true;
#ifdef LOCAL
		convert += "{";
		for (const auto& element : elements)
		{
			if (!first) convert += ", ";
			first = false;
			convert += std::to_string(element);
		}
		convert += "}";
#else
		for (const auto& element : elements)
		{
			if (!first) convert += " ";
			first = false;
			convert += std::to_string(element);
		}
#endif
		return convert;
	}
}

// INPUT
template<typename Arg, typename... Args> void read(std::istream& in, Arg& first, Args& ... rest);
template<typename T1, typename T2> void read(std::istream& in, std::pair<T1, T2>& element);
template<typename T, std::size_t Size> void read(std::istream& in, std::array<T, Size>& elements);
template<typename T> void read(std::istream& in, double& element);
template<typename T> void read(std::istream& in, long double& element);
template<typename T> void read(std::istream& in, std::complex<T>& element);
template<typename T> void read(std::istream& in, std::vector<T>& elements);
template<typename T> void read(std::istream& in, T& element);

template<typename Arg, typename... Args>
void read(std::istream& in, Arg& first, Args& ... rest)
{
	read(in, first);
	read(in, rest...);
}

template<typename T1, typename T2>
void read(std::istream& in, std::pair<T1, T2>& element)
{
	read(in, element.first, element.second);
}

template<typename T, std::size_t Size>
void read(std::istream& in, std::array<T, Size>& elements)
{
	for (auto& element : elements) read(in, element);
}

void read(std::istream& in, double& element)
{
	std::string convert;
	read(in, convert);
	element = std::stod(convert);
}

void read(std::istream& in, long double& element)
{
	std::string convert;
	read(in, convert);
	element = std::stold(convert);
}

template<typename T>
void read(std::istream& in, std::complex<T>& element)
{
	T first, second;
	read(in, first, second);
	element = std::complex<T>(first, second);
}

template<typename T>
void read(std::istream& in, std::vector<T>& elements)
{
	for (auto& element : elements) read(in, element);
}

template<typename T>
void read(std::istream& in, T& element)
{
	in >> element;
}

// OUTPUT
template<typename Arg, typename... Args> void print(std::ostream& out, const Arg& first, const Args& ... rest);
template<typename Arg, typename... Args> void prints(std::ostream& out, const Arg& first, const Args& ... rest);
template<typename T> void print(std::ostream& out, const T& element);
void prints(std::ostream& out);

template<typename Arg, typename... Args>
void print(std::ostream& out, const Arg& first, const Args& ... rest)
{
	print(out, first);
	print(out, rest...);
}

template<typename Arg, typename... Args>
void prints(std::ostream& out, const Arg& first, const Args& ... rest)
{
	print(out, first);
	if (sizeof...(rest)) print(out, " ");
	prints(out, rest...);
}

template<typename T>
void print(std::ostream& out, const T& element)
{
	out << std::to_string(element);
}

void prints(std::ostream& out)
{
	print(out, '\n');
}

void setIO()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
#ifdef LOCAL
	std::cin.exceptions(std::ios::eofbit | std::ios::failbit | std::ios::badbit);
#endif
}

#endif
using namespace std;

constexpr long long MAXN __attribute__((unused)) = static_cast<long long>(2 * 1e5 + 1);
constexpr long long INF __attribute__((unused)) = static_cast<long long>(1e18 + 1);
constexpr long long MOD __attribute__((unused)) = static_cast<long long>(1e9 + 7);
constexpr long double EPS __attribute__((unused)) = static_cast<long double>(1e-7);

#ifndef COMPRESS_HPP
#define COMPRESS_HPP

#ifndef CHASH_HPP
#define CHASH_HPP

#include <cstddef>
#include <cstdint>

// https://codeforces.com/blog/entry/62393
struct chash
{
	// http://xorshift.di.unimi.it/splitmix64.c
	static std::uint64_t splitmix64(std::uint64_t x)
	{
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30ULL)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27ULL)) * 0x94d049bb133111eb;
		return x ^ (x >> 31ULL);
	}

	std::size_t operator()(std::uint64_t x) const
	{
		static const std::uint64_t
				FIXED_RANDOM = static_cast<std::uint64_t>(std::chrono::steady_clock::now().time_since_epoch()
				.count());
		return splitmix64(x + FIXED_RANDOM);
	}

	std::size_t operator()(std::pair<std::uint64_t, std::uint64_t> x) const
	{
		static const std::uint64_t
				FIXED_RANDOM = static_cast<std::uint64_t>(std::chrono::steady_clock::now().time_since_epoch()
				.count());
		return splitmix64(x.first + FIXED_RANDOM) ^ (splitmix64(x.second + FIXED_RANDOM) >> 1ULL);
	}
};

#endif

template<typename T>
std::size_t compress(std::vector<T>& elements)
{
	std::set<T> orderedElements;
	for (const auto& element : elements)
		orderedElements.insert(element);
	__gnu_pbds::gp_hash_table<T, std::size_t, chash> indices;
	std::size_t index = 0;
	for (const auto& element : orderedElements)
		indices[element] = index++;
	for (auto& element : elements)
		element = indices[element];
	return index;
}

#endif
#ifndef BIT_HPP
#define BIT_HPP

// Verification:
// https://judge.yosupo.jp/submission/17528/




template<class T>
class BIT
{
	std::vector<T> m_tree;
public:
	explicit BIT(const std::size_t& size)
	{
		m_tree.assign(size + 1, 0);
	}

	void update(std::size_t i, const T& delta)
	{
		for (++i; i < m_tree.size(); i += (i & (-i)))
			m_tree[i] += delta;
	}

	T query(std::size_t i)
	{
		T sum = 0;
		for (++i; i; i -= (i & (-i)))
			sum += m_tree[i];
		return sum;
	}

	T query(const std::size_t& i, const std::size_t& j)
	{
		return query(j) - (i ? query(i - 1) : 0);
	}
};

#endif

class FRangeSetQuery
{
public:
	void solve(std::istream& in, std::ostream& out)
	{
		size_t n, q;
		read(in, n, q);
		vector<ll> c(n);
		read(in, c);
		for (auto& ball : c)
			--ball;
		vector<tuple<size_t, size_t, size_t>> queries;
		for (size_t i = 0; i < q; ++i)
		{
			size_t l, r;
			read(in, l, r);
			queries.eb(r - 1, l - 1, i);
		}
		FSRT(queries);
		BIT<ll> bit(n);
		vector<ll> last(n, -1), answers(q);
		size_t index = 0;
		for (size_t i = 0; i < n; ++i)
		{
			if (last[c[i]] != -1)
				bit.update(last[c[i]], -1);
			bit.update(last[c[i]] = i, 1);
			while (index < q && get<0>(queries[index]) == i)
			{
				answers[get<2>(queries[index])] = bit.query(get<1>(queries[index]), get<0>(queries[index]));
				++index;
			}
		}
		for (const auto& answer : answers)
			prints(out, answer);
	}
};

int main()
{
	setIO();
	FRangeSetQuery solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	std::fflush(stdout);
	return 0;
}

Measured memory_bytes: 31132