const main = (input) => {
  input = input.trim().split('\n').map(v => v.split(' ').map(Number))
  // const [n, q] = input[0].split(' ').map(Number)
  const stones = input[1]
  const [, , ...q] = input

  const ans = {}
  const sq = q.slice(0).sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0])

  while (sq.length) {

    const [start, end] = sq.shift()

    const s = new Set(stones.slice(start-1, end))
    ans[`${start}-${end}`] = s.size

    while (sq[0] && sq[0][0] === start) {
      const [_start, _end] = sq.shift()
      for (let i = end; i < _end; i++) s.add(stones[i])
      ans[`${_start}-${_end}`] = s.size
    }
  }

  for (let [s, e] of q) console.log(ans[`${s}-${e}`])
}

process.env.MYTEST ? test() : main(require('fs').readFileSync('/dev/stdin', 'utf8'))