#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Wavelet {
public:
    explicit Wavelet(const vector<unsigned int>& a) : N(a.size()), vb(getDigits_(a), BitVector(a.size())){
        vector<unsigned int> v = a;
        vector<unsigned int> v0(N), v1(N);
        for(int i=vb.size()-1;i>=0;i--){
            maxVal = 2 * maxVal + 1;
            int idx0 = 0, idx1 = 0;
            for(int j=0;j<N;j++){
                if(v[j]&(1<<i)){
                    v1[idx1++] = v[j];
                    vb[i].set(j);
                } else {
                    v0[idx0++] = v[j];
                }
            }
            for(int j=0;j<idx0;j++) v[j]      = v0[j];
            for(int j=0;j<idx1;j++) v[j+idx0] = v1[j];
            vb[i].build();
        }
    }
    int getLeqNum(int val, int end){
        if(end <= 0) return 0;
        if(val < 0) return 0;
        val = min(val, maxVal);
        int res = 0;
        int offset = 0, num = end-1;
        for(int i=vb.size()-1;i>=0;i--){
            if(num < offset) break;
            int rank1 = vb[i].rank(num) - vb[i].rank(offset-1);
            int rank0 = num-offset+1-rank1;
            if(val&(1<<i)){
                if(i == 0) return res + num-offset+1;
                res += rank0;
                offset = N - vb[i].rank(N) + vb[i].rank(offset-1);
                num = offset + rank1 - 1;
            } else {
                if(i == 0) return res + rank0;
                offset = offset - vb[i].rank(offset-1);
                num = offset + rank0 - 1;
            }
        }
        return res;
    }
private:
    int getDigits_(const vector<unsigned int>& a){
        int m = *max_element(a.begin(), a.end());
        int res = 0;
        while(m){ ++res; m /= 2; }
        return max(1, res);
    }
    class BitVector{
    public:
        explicit BitVector(int n=0) : bit((n+63)/64) {}
        void set(int p){
            while(p/64 >= bit.size()) bit.emplace_back(0ULL, 0);
            bit[p/64].first |= 1ULL << (p%64);
        }
        bool get(int p) const {
            if(p/64 >= bit.size()) return false;
            return bit[p/64].first & (1ULL << p%64);
        }
        void build(){
            for(int i=1;i<bit.size();i++)
                bit[i].second = bit[i-1].second + bitCount_(bit[i-1].first);
        }
        int rank(int p) const {
            if(p < 0 || bit.size() == 0) return 0;
            if(p/64 >= bit.size()) return bit.back().second + bitCount_(bit.back().first);
            if(p%64 == 63) return bit[p/64].second + bitCount_(bit[p/64].first);
            return bit[p/64].second + bitCount_(bit[p/64].first & (1ULL << p%64+1)-1);
        }
    private:
        vector<pair<unsigned long long, int>> bit;
        int bitCount_(unsigned long long t) const {
            t = (t&0x5555555555555555ULL)+((t>>1)&0x5555555555555555ULL);
            t = (t&0x3333333333333333ULL)+((t>>2)&0x3333333333333333ULL);
            t = (t&0x0f0f0f0f0f0f0f0fULL)+((t>>4)&0x0f0f0f0f0f0f0f0fULL);
            t = (t&0x00ff00ff00ff00ffULL)+((t>>8)&0x00ff00ff00ff00ffULL);
            t = (t&0x0000ffff0000ffffULL)+((t>>16)&0x0000ffff0000ffffULL);
            t = (t&0x00000000ffffffffULL)+((t>>32)&0x00000000ffffffffULL);
            return t;
        }
    };
private:
    const int N;
    int maxVal = 0;
    vector<BitVector> vb;
};

int main(){
    int N, Q; cin >> N >> Q;
    vector<int> last(N, -1);
    vector<unsigned int> a(N, 0);
    for(int i=0;i<N;i++){
        int t; cin >> t;
        --t;
        if(last[t] != -1) a[i] = last[t] + 1;
        last[t] = i;
    }
    Wavelet wav(a);
    for(int i=0;i<Q;i++){
        int l, r; cin >> l >> r;
        --l;
        cout << r - l - (wav.getLeqNum(r, r) - wav.getLeqNum(l, r)) << endl;
    }
}

#include <bits/stdc++.h>

struct FastIO {
  FastIO() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
  }
} fast_io;

#if DEBUG
template <typename T>
void debug(const T& value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(const T& value, const Ts&... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                        \
  do {                                  \
    cerr << #__VA_ARGS__ << ": ";       \
    debug(__VA_ARGS__);                 \
    cerr << " (L" << __LINE__ << ")\n"; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define rd(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << '\n';
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define wt(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;
#include <math.h>

template <typename T, class DS>
class Mo {
 public:
  Mo(DS& ds) : ds_(ds) {}
  void AddQuery(int begin, int end) {
    int index = queries_.size();
    queries_.push_back({begin, end, index});
  }
  std::vector<T> ProcessQueries() {
    int bin = sqrt(queries_.size());
    sort(queries_.begin(), queries_.end(),
         [&bin](const Query& a, const Query& b) {
           int c = a.begin / bin, d = b.begin / bin;
           if (c != d) return c < d;
           if (c % 2 == 0) {
             return a.end < b.end;
           }
           return a.end > b.end;
         });
    std::vector<T> ret(queries_.size());
    Query p = {0, 0, 0};
    for (std::size_t i = 0; i < queries_.size(); ++i) {
      const Query& c = queries_[i];
      Add(c.begin, p.begin);
      Del(p.begin, c.begin);
      Add(p.end, c.end);
      Del(c.end, p.end);
      ret[c.index] = ds_.Get();
      p = c;
    }
    return ret;
  }

 private:
  struct Query {
    int begin, end, index;
  };
  void Add(int begin, int end) {
    for (int i = begin; i < end; ++i) {
      ds_.Add(i);
    }
  }
  void Del(int begin, int end) {
    for (int i = begin; i < end; ++i) {
      ds_.Del(i);
    }
  }
  DS& ds_;
  std::vector<Query> queries_;
};

using namespace std;

struct DS {
  DS(int n) : c(n), kinds(n), unique_kinds(0) {}
  void Add(int i) {
    if (kinds[c[i] - 1]++ == 0) {
      ++unique_kinds;
    }
  }
  void Del(int i) {
    if (--kinds[c[i] - 1] == 0) {
      --unique_kinds;
    }
  }
  int Get() const { return unique_kinds; }
  V<int> c;
  V<int> kinds;
  int unique_kinds;
};

int main() {
  rd(int, n, q);
  DS ds(n);
  rep(i, n) cin >> ds.c[i];

  Mo<int, DS> mo(ds);
  rep(i, q) {
    rd(int, l, r);
    mo.AddQuery(l - 1, r);
  }

  for (int ans : mo.ProcessQueries()) {
    wt(ans);
  }
}
