class Bit {
  constructor(n) {
    this.n = n;
    this.d = new Array(n+1).fill(0);
  }
  add(i, x=1) {
    // https://www.quora.com/What-does-I+-I-l-mean-in-bitwise-programming
    for (i++; i<=this.n; i+=i&-i) {
      this.d[i] += x;
    }
  }
  _sum(i) {
    let x = 0;
    for (i++; i; i -= i&-i) {
      x += this.d[i];
    }
    return x;
  }
  sum(l, r) {
    return this._sum(r-1) - this._sum(l-1);
  }
}
function Main(input) {
  input = input.split("\n");
  const [n, q] = input.shift().split(" ").map((a) => parseInt(a, 10));
  const a = input.shift().split(" ").map((a) => parseInt(a, 10));
  // store the information whether the number is already appeared
  const pi = new Array(n+1).fill(-1);
  const ps = new Array(n+1);
  for(let i=0; i<ps.length; i++) {
    ps[i] = [];
  }
  for (let i=0; i<n; i++) {
    const l = pi[a[i]];
    if (l !== -1) {
      ps[l].push(i);
    }
    pi[a[i]] = i;
  }

  // Preload queries
  const qs = new Array(n+1);
  for(let i=0; i<qs.length; i++) {
    qs[i] = [];
  }
  for (let qi=0; qi<q; qi++) {
    let [l, r] = input[qi].split(" ").map((a) => parseInt(a, 10));
    --l;
    --r;
    qs[l].push([r, qi]);
  }
  const ans = [];
  const d = new Bit(n);
  for (let x=n-1; x>=0; --x) {
    ps[x].forEach((y) => {
      d.add(y, 1);
    });
    qs[x].forEach((query) => {
      const [r, i] = query;
      ans[i] = (r-x+1) - d._sum(r);
    });
  }
  for (let i=0; i<q; i++) {
    console.log(ans[i]);
  }
  return;
}

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