process.stdin.resume();
process.stdin.setEncoding('utf-8');
 
let inputString = '';
let currentLine = 0;
 
process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});
 
process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(string => {
        return string.trim();
    });
    
    main();    
});
 
function readLine() {
    return inputString[currentLine++];
}

function main() {
  const [n, q] = readLine().split(/\s/).map(Number)
  const cs = readLine().split(/\s/).map(Number)
  const original = []
  for (let i = 0; i < q; i++) {
    original.push(readLine())
  }
  const qs = original
    .map(s => s.split(/\s/).map(Number))
    .sort((a, b) => a[1] - b[1] || a[0] - b[0])
  const lastIndices = Array(n).fill(0)
  const sums = []
  let currentR = 1
  const results = {}
  for (const [l, r] of qs) {
    for (let i = currentR; i <= r; i++) {
      const color = cs[i - 1]
      const last = lastIndices[color]
      lastIndices[color] = i
      for (let j = last; j < i; j++) {
        sums[j] = (sums[j] || 0) + 1
      }
    }
    currentR = r
    results[`${l} ${r}`] = sums[l - 1]
  }
  for (const o of original) {
    console.log(results[o])
  }
}