#include <bits/stdc++.h>

using namespace std;

namespace fast {
const int BSZ = 1 << 15; ////// INPUT
char ibuf[BSZ];
int ipos, ilen;

char nc() { // next char
  if (ipos == ilen) {
    ipos = 0;
    ilen = fread(ibuf, 1, BSZ, stdin);
    if (!ilen)
      return EOF;
  }
  return ibuf[ipos++];
}

void rs(string &x) { // read string
  char ch;
  while (isspace(ch = nc()))
    ;
  do {
    x += ch;
  } while (!isspace(ch = nc()) && ch != EOF);
}

template <class T> void ri(T &x) { // read int or ll
  char ch;
  int sgn = 1;
  while (!isdigit(ch = nc()))
    if (ch == '-')
      sgn *= -1;
  x = ch - '0';
  while (isdigit(ch = nc()))
    x = x * 10 + (ch - '0');
  x *= sgn;
}

template <class T, class... Ts> void ri(T &t, Ts &... ts) {
  ri(t);
  ri(ts...);
} // read ints
  ////// OUTPUT (call initO() at start)
char obuf[BSZ], numBuf[100];
int opos;

void flushOut() {
  fwrite(obuf, 1, opos, stdout);
  opos = 0;
}

void wc(char c) { // write char
  if (opos == BSZ)
    flushOut();
  obuf[opos++] = c;
}

void ws(string s) {
  for (char c : s)
    wc(c);
} // write string
template <class T> void wi(T x, char after = '\0') { /// write int
  if (x < 0)
    wc('-'), x *= -1;
  int len = 0;
  for (; x >= 10; x /= 10)
    numBuf[len++] = '0' + (x % 10);
  wc('0' + x);
  for (int i = len - 1; i >= 0; i--)
    wc(numBuf[i]);
  if (after)
    wc(after);
}

void initO() { assert(atexit(flushOut) == 0); } /// auto-flush output
} // namespace fast
using namespace fast;

// Globals
const int mxn = 500005;
int a[mxn], freq[mxn] = {};

class query {
public:
  int s, e, i, b;
  query() { s = e = i = b = INT_MAX; }
  query(int start, int end, int index, int block) {
    s = start, e = end, i = index, b = block;
  }
};

class querySolver {
public:
  int sz;
  vector<query> queries;

  querySolver(int q) {
    sz = 0;
    queries.resize(q);
  }

  void addQuery(int s, int e, int i, int b) {
    queries[sz++] = query(s, e, i, b);
  }

  void solve() {
    sort(queries.begin(), queries.end(), [](query &q1, query &q2) -> bool {
      if (q1.b == q2.b)
        return q1.e < q2.e;
      return q1.b < q2.b;
    });
    vector<int> res(sz);
    int l = queries[0].s, r = queries[0].e, cnt = 0;
    for (int i = l; i <= r; i++) {
      freq[a[i]]++;
      if (freq[a[i]] == 1)
        cnt++;
    }
    res[queries[0].i] = cnt;
    for (int i = 1; i < sz; i++) {
      int nL = queries[i].s, nR = queries[i].e;
      if (l < nL) {
        // Remove elements
        while (l < nL) {
          freq[a[l]]--;
          if (!freq[a[l]])
            cnt--;
          l++;
        }
      } else if (l > nL) {
        // Add elements
        while (l > nL) {
          l--;
          freq[a[l]]++;
          if (freq[a[l]] == 1)
            cnt++;
        }
      }
      if (r < nR) {
        // Add elements
        while (r < nR) {
          r++;
          freq[a[r]]++;
          if (freq[a[r]] == 1)
            cnt++;
        }
      } else if (r > nR) {
        // Remove elements
        while (r > nR) {
          freq[a[r]]--;
          if (!freq[a[r]])
            cnt--;
          r--;
        }
      }
      res[queries[i].i] = cnt;
    }
    for (auto &ans : res)
      wi(ans, '\n');
  }
};

int main() {
  initO();
  int n, q;
  ri(n, q);
  // Coordinate Compression
  unordered_map<int, int> compressor;
  for (int i = 0, nVal = 1; i < n; i++) {
    ri(a[i]);
    if (compressor.count(a[i])) {
      a[i] = compressor[a[i]];
    } else {
      compressor[a[i]] = nVal;
      a[i] = nVal++;
    }
  }
  // Queries
  auto qSolver = querySolver(q);
  int block = sqrt(n);
  for (int i = 0, start, end; i < q; i++) {
    ri(start, end);
    start--, end--;
    qSolver.addQuery(start, end, i, start / block);
  }
  qSolver.solve();
  return 0;
}

Measured memory_bytes: 37144