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



// Taken from: https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/templateShort.cpp

#include <utility>
#include <vector>
#include <random>
#include <chrono>
#include <cassert>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <complex>
#include <stack>
#include <array>
#include <unordered_set>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pii;

typedef vector<int> vi;
typedef vector<ull> vul;
typedef vector<ll> vl;
typedef vector<pii> vpii;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5;

template<class T> bool ckmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; }

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());


//
// Created by aryssoncf on 28/10/2019.
//

#include <type_traits>


#include <iterator>


template <typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
    return true;
}

constexpr bool hasBegin(...) {
    return false;
}

template <typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;


#ifndef JHELPER_EXAMPLE_PROJECT_IO_HPP
#define JHELPER_EXAMPLE_PROJECT_IO_HPP

#endif //JHELPER_EXAMPLE_PROJECT_IO_HPP

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &vec) {
    for (T &element: vec) {
        is >> element;
    }
    return is;
}

template<typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first;
    is >> p.second;
    return is;
}

template <class X, class Y>
std::ostream & operator << (std::ostream & os, std::pair <X, Y> const& p) {
    return os << p.first << " " << p.second;
}

template <class Ch, class Tr, class Container>
std::basic_ostream <Ch, Tr> & operator << (std::basic_ostream <Ch, Tr>& os, Container const& x) {
    bool first = true;
    for(auto& y : x) {
        if (first) {
            first = false;
        } else {
            os << " ";
        }
        os << y;
    }
    return os;
}


#include <functional>




#include <string>
#include <stdexcept>

#ifndef SPCPPL_ASSERT
#ifdef SPCPPL_DEBUG
#define SPCPPL_ASSERT(condition) \
		if(!(condition)) { \
			throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
		}
#else
#define SPCPPL_ASSERT(condition)
#endif
#endif






template <typename T, typename Merge>
class SegmentTreeBase {
protected:
    explicit SegmentTreeBase(std::size_t n, const T& defaultValue = T(), const Merge& merge = Merge()):
            n(n),
            defaultValue(defaultValue),
            shift(calculateShift(n)),
            values(shift << 1, defaultValue),
            merge(merge) {

    }

    template <typename R, typename = enable_if_t<IsContainer<R>::value>>
    explicit SegmentTreeBase(const R& range, const T& defaultValue = T(), const Merge& merge = Merge()) :
            SegmentTreeBase(
                    static_cast<std::size_t>(std::distance(std::begin(range), std::end(range))),
                    defaultValue,
                    merge
            ) {
        std::copy(std::begin(range), std::end(range), values.begin() + shift);
        for (size_t index = shift - 1; index > 0; --index) {
            recalculate(index);
        }
    }

    static std::size_t calculateShift(std::size_t n) {
        std::size_t result = 1;
        while (result < n) {
            result <<= 1;
        }
        return result;
    }

    void recalculate(std::size_t index) {
        values[index] = merge(values[2 * index], values[2 * index + 1]);
    }

    std::size_t n;
    T defaultValue;
    std::size_t shift;
    std::vector<T> values;
    Merge merge;
};


template <typename T, typename Merge>
class BottomUpSegmentTree: protected SegmentTreeBase<T, Merge> {
public:

    template <typename R>
    explicit BottomUpSegmentTree(const R& range, const T& defaultValue = T(), const Merge& merge = Merge()):
            SegmentTreeBase<T, Merge>(range, defaultValue, merge) {

    }

    const T& getElement(std::size_t index) {
//        SPCPPL_ASSERT(index < n);
        return values[index + shift];
    }

    T getResult(std::size_t l, std::size_t r) const {
//        SPCPPL_ASSERT(l <= r && r <= n);
        return internalGetResult(l + shift, r + shift);
    }

    template <typename Updater>
    void update(std::size_t index, const Updater& updater) {
//        SPCPPL_ASSERT(index < n);
        index += shift;
        updater(values[index]);
        for (std::size_t parent = index / 2; parent > 0; parent /= 2) {
            this->recalculate(parent);
        }
    }

    void set(std::size_t index, const T& value) {
        return update(index, [&value](T& element) {
            element = value;
        });
    }

protected:
    using Base = SegmentTreeBase<T, Merge>;
    using Base::n;
    using Base::defaultValue;
    using Base::shift;
    using Base::values;
    using Base::merge;

private:
    T internalGetResult(std::size_t l, std::size_t r) const {
        if (l == r) {
            return defaultValue;
        }
        if (l & 1) {
            return merge(values[l], internalGetResult(l + 1, r));
        }
        if (r & 1) {
            return merge(internalGetResult(l, r - 1), values[r - 1]);
        }
        return internalGetResult(l / 2, r / 2);
    }
};


template <typename T>
class BottomUpSumSegmentTree: public BottomUpSegmentTree<T, std::plus<T>> {
public:
    template <typename R>
    explicit BottomUpSumSegmentTree(
            const R& range,
            const T& zero = T()
    ): BottomUpSegmentTree<T, std::plus<T>>(range, zero) {
    }

};

using namespace std;

class FRangeSetQuery {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int n, q;
	    in >> n >> q;
	    vi C(n);
	    in >> C;
	    trav(x, C) {
	        x--;
	    }
	    vi pos(n, -1);
	    vpii queries(q);
	    in >> queries;
	    vi id(q), res(q);
	    iota(all(id), 0);
	    trav(qu, queries) {
	        qu.f--;
	    }
	    sort(all(id), [&](int A, int B) {
	        return queries[A].s < queries[B].s;
	    });
	    int idx = 0;
	    BottomUpSumSegmentTree<int> seg((vi(n)));
	    trav(i, id) {
	        int l, r;
	        tie(l, r) = queries[i];
	        while (idx < r) {
	            int x = C[idx];
	            if (pos[x] != -1) {
	                seg.set(pos[x], 0);
	            }
	            seg.set(idx, 1);
	            pos[x] = idx;
	            idx++;
	        }
	        res[i] = seg.getResult(l, r);
	    }
	    trav(x, res) {
	        out << x << '\n';
	    }
	}

	void setup() {}
};


int main() {
    std::ios_base::sync_with_stdio(false);
	FRangeSetQuery solver;
    solver.setup();
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 21120