package main

import (
	"io"
	"os"
	"strconv"
)

var data []byte
var ptr int

func nextInt() int {
	n := len(data)
	for ptr < n && (data[ptr] < '0' || data[ptr] > '9') {
		ptr++
	}
	x := 0
	for ptr < n && data[ptr] >= '0' && data[ptr] <= '9' {
		x = x*10 + int(data[ptr]-'0')
		ptr++
	}
	return x
}

var seg []int
var segSize int

func findLast(node, l, r, limit, prev int) int {
	if l > limit || seg[node] <= prev {
		return 0
	}
	if l == r {
		return l
	}
	mid := (l + r) >> 1
	if limit > mid {
		res := findLast(node<<1|1, mid+1, r, limit, prev)
		if res != 0 {
			return res
		}
	}
	return findLast(node<<1, l, mid, limit, prev)
}

var bit []int
var bitN int

func add(i, v int) {
	for i <= bitN {
		bit[i] += v
		i += i & -i
	}
}

func sum(i int) int {
	s := 0
	for i > 0 {
		s += bit[i]
		i -= i & -i
	}
	return s
}

func main() {
	data, _ = io.ReadAll(os.Stdin)

	n := nextInt()
	q := nextInt()

	occ := make([]bool, n+1)
	lastOcc := make([]int, n+1)

	segSize = 1
	for segSize < n {
		segSize <<= 1
	}
	seg = make([]int, segSize<<1)

	headGap := make([]int, n+2)
	gapX := make([]int, n+1)
	gapNext := make([]int, n+1)
	gapCnt := 0

	for i := 1; i <= n; i++ {
		x := nextInt()
		occ[x] = true
		prev := lastOcc[x]
		if prev != 0 && x > 1 {
			g := findLast(1, 1, segSize, x-1, prev)
			if g != 0 {
				gapCnt++
				gapX[gapCnt] = x
				gapNext[gapCnt] = headGap[g]
				headGap[g] = gapCnt
			}
		}
		lastOcc[x] = i
		p := segSize + x - 1
		for p > 0 {
			seg[p] = i
			p >>= 1
		}
	}

	prefDistinct := make([]int, n+1)
	for i := 1; i <= n; i++ {
		prefDistinct[i] = prefDistinct[i-1]
		if occ[i] {
			prefDistinct[i]++
		}
	}

	headQuery := make([]int, n+2)
	qR := make([]int, q+1)
	qNext := make([]int, q+1)
	ans := make([]int, q+1)

	for i := 1; i <= q; i++ {
		l := nextInt()
		r := nextInt()
		qR[i] = r
		qNext[i] = headQuery[l]
		headQuery[l] = i
	}

	bitN = n
	bit = make([]int, n+2)

	for l := n; l >= 1; l-- {
		for e := headGap[l]; e != 0; e = gapNext[e] {
			add(gapX[e], 1)
		}
		base := prefDistinct[l-1]
		for id := headQuery[l]; id != 0; id = qNext[id] {
			r := qR[id]
			ans[id] = prefDistinct[r] - base + sum(r)
		}
	}

	out := make([]byte, 0, q*8)
	for i := 1; i <= q; i++ {
		out = strconv.AppendInt(out, int64(ans[i]), 10)
		out = append(out, '\n')
	}
	os.Stdout.Write(out)
}