object Main extends App {
  val sc = new FastScanner(System.in)
  val n, q = sc.nextInt()
  val c = Array.fill(n)(sc.nextInt()-1)
  val lr = List.fill(q)((sc.nextInt()-1, sc.nextInt()-1))
  val ans = Array.fill(q)(0)

  val pos = Array.fill(n)(-1)
  val bit = new BinaryIndexedTree(n)
  var lPrev = n

  for (((l, r), idx) <- lr.zipWithIndex.sortBy(-_._1._1)) {
    for (i <- lPrev-1 to l by -1) {
      val ci = c(i)
      val p = pos(ci)
      pos(ci) = i
      if (p != -1) {
        bit.add(p, -1)
      }
      bit.add(i, 1)
    }
    lPrev = l
    ans(idx) = bit.query(r+1)
  }

  val pw = new java.io.PrintWriter(Console.out)
  ans.foreach(pw.println)
  pw.flush()
}

class BinaryIndexedTree(n: Int) {
  private val tree = Array.fill(n+1)(0)

  def query(r: Int): Int = {
    var res = 0
    var i = r
    while (i > 0) {
      res += tree(i)
      i -= i & -i
    }
    res
  }

  def add(idx: Int, a: Int): Unit = {
    var i = idx+1
    while (i <= n) {
      tree(i) += a
      i += i & -i
    }
  }
}

class FastScanner(source: java.io.InputStream) {
  val buf = new Array[Byte](1024)
  var now, end = 0

  def isPrintable(b: Byte): Boolean = 33 <= b && b <= 126
  def isNum(b: Byte): Boolean = 48 <= b && b <= 57

  def hasNextByte: Boolean = {
    if (now < end) {
      true
    } else {
      now = 0
      end = source.read(buf)
      end > 0
    }
  }

  def nextByte(): Byte = {
    if (hasNextByte) {
      val b = buf(now)
      now += 1
      b
    } else {
      -1
    }
  }

  def hasNext: Boolean = {
    while (hasNextByte && !isPrintable(buf(now))) {
      now += 1
    }
    hasNextByte
  }

  def next(): String = {
    if (hasNext) {
      val sb = new StringBuilder()
      var b = nextByte()
      while (isPrintable(b)) {
        sb += b.toChar
        b = nextByte()
      }
      sb.toString
    } else {
      throw new NoSuchElementException()
    }
  }

  def nextInt(): Int = {
    nextLong().toInt
  }

  def nextLong(): Long = {
    if (hasNext) {
      var b = nextByte()
      var sign = 1
      var n = 0L
      if (b == '-') {
        sign = -1
        b = nextByte()
      }
      while (isNum(b)) {
        n = n * 10 + (b - 48)
        b = nextByte()
      }
      sign * n
    } else {
      throw new NoSuchElementException()
    }
  }

  def nextDouble(): Double = next().toDouble
}
