// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

int res = 0;

// Mo のアルゴリズム (以下の条件を満たすときにクエリを高速に処理可能)
// ・オフラインクエリ
// ・クエリの対象となる数列が不変
// ・区間の伸縮にかかる計算量が小さい
struct Mo {
    int bucket, nl, nr, ptr;
    vector<int> left, right, query_idx;
    vector<bool> state;

    Mo(int N) : bucket(1500), nl(0), nr(0), ptr(0), state(N) {
        left = right = vector<int>();
        left.reserve(500010);
        right.reserve(500010);
    }

    // 区間 [l, r) を追加
    void insert(int l, int r) {
        left.push_back(l);
        right.push_back(r);
    }

    // ソートする (バケットごとに、バケット同じなら右端小さい順)
    void build() {
        query_idx = vector<int>(left.size());
        iota(query_idx.begin(), query_idx.end(), 0);
        sort(query_idx.begin(), query_idx.end(), [&](int a, int b) {
                if(left[a] / bucket != left[b] / bucket) return left[a] < left[b];
                return right[a] < right[b];
            });
    }
    
    // クエリを一つすすめて、そのクエリ id を返す
    vector<int> run() {
        vector<int> ans(query_idx.size());

        auto operate = [&](int idx) {
            state[idx].flip();
            if(state[idx]) add(idx);
            else del(idx);
        };
        
        for(size_t i=0; i<query_idx.size(); i++) {
            int id = query_idx[ptr++];
            while(nl > left[id] ) operate(--nl);
            while(nr < right[id]) operate(nr++);
            while(nl < left[id] ) operate(nl++);
            while(nr > right[id]) operate(--nr);
            ans[id] = res;
        }
        return ans;
    }

    inline void add(int idx) const;
    inline void del(int idx) const;
};

int A[500010], cnt[500010];
inline void Mo::add(int idx) const {
    if(cnt[ A[idx] ]++ == 0) ++res;
}

inline void Mo::del(int idx) const {
    if(cnt[ A[idx] ]-- == 1) --res;
}

class FastIO {
  static const int rdata_sz = (1 << 25), wdata_sz = (1 << 25);
  char rdata[rdata_sz], wdata[wdata_sz], *rb, *wb;
  char tmp_s[20];

public:
  FastIO() {
    fread(rdata, 1, rdata_sz, stdin);
    rb = rdata; wb = wdata;
  }
  ~FastIO() {
    fwrite(wdata, 1, wb - wdata, stdout);
  }

  template<typename T>
  inline void read_i(T &x) {
    bool neg = false;
    x = 0;
    while((*rb < '0' || *rb > '9') && *rb != '-') ++rb;
    if(*rb == '-') {
      neg = true;
      ++rb;
    }
    while('0' <= *rb && *rb <= '9') {
      x = 10 * x + (*rb - '0');
      ++rb;
    }
    if(neg) x = -x;
  }

#define pc(x) *(wb++) = x
  template<typename T>
  inline void writeln_i(T x) {
    if (x == 0) { pc('0'); pc('\n'); return; }
    if(x < 0) { pc('-'); x = -x; }
    char *t = tmp_s;
    while(x) {
      T y = x / 10;
      *(t++) = (x - y*10) + '0';
      x = y;
    }
    while(t != tmp_s) pc(*(--t));
    pc('\n');
  }
#undef pc
};
FastIO io;

int main() {
    int N; io.read_i(N);
    int Q; io.read_i(Q);
    for(int i=0; i<N; i++) {
        io.read_i(A[i]);
    }

    Mo mo(N);
    for(int i=0; i<Q; i++) {
        int l; io.read_i(l);
        int r; io.read_i(r);
        mo.insert(--l, r);
    }

    mo.build();
    vector<int> ans = mo.run();
    for(int i=0; i<Q; i++) {
        io.writeln_i(ans[i]);
    }
    return 0;
}


Measured memory_bytes: 27956