function Main(input) {
  input = input.split("\n");
  const nq = input.shift().split(" ");
  const n = parseInt(nq[0], 10);
  const q = parseInt(nq[1], 10);
  const cs = input.shift().split(" ");

  // Preload queries
  const qs = [];
  for (let qi=0; qi<q; qi++) {
    const [l, r] = input[qi].split(" ");
    qs[l-1] = qs[l-1] || [];
    qs[l-1].push([r-1, qi]);
  }

  // store the information whether the number is already appeared
  const ps = [];
  const pi = {};
  for (let i=0; i<n; i++) {
    const l = pi[cs[i]];
    if (l !== undefined) {
      ps[l] = ps[l] || [];
      ps[l].push(i);
    }
    pi[cs[i]] = i;
  }

  const ans = [];

  // Create BIT
  const d = [];
  for (let x=n-1; x>=0; --x) {
    const psLength = ps[x] && ps[x].length || 0;
    for (let y=0; y<psLength; y++) {
      let di = ps[x][y] + 1;
      for (; di<=n; di+=di&-di) {
        d[di] = d[di] || 0;
        d[di] += 1;
      }
    }
    const qsLength = qs[x] && qs[x].length || 0;
    for (let y=0; y<qsLength; y++) {
      const [r, i] = qs[x][y];
      let sum = 0;
      let ri = r + 1;
      for (; ri; ri -= ri&-ri) {
        sum += d[ri] || 0;
      }
      ans[i] = (r-x+1) - sum;
    }
  }

  console.log(ans.join("\n"));
  return;
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));
