package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	q := iScan()
	c := iSScan(n)
	lr := make([][2]int, q)
	for i := 0; i < q; i++ {
		lr[i][0], lr[i][1] = iScan()-1, iScan()
	}
	lrc := make([][2]int, q)
	copy(lrc, lr)
	sort.Slice(lrc, func(i, j int) bool { return lrc[i][1] < lrc[j][1] })
	R := 0
	lastAppeared := make([]int, max(c)+1)
	for i, _ := range lastAppeared {
		lastAppeared[i] = -1
	}
	seg := InitSegmentTree(make([]int, n), 0)
	ans := make(map[[2]int]int)
	for _, v := range lrc {
		for i := R; i < v[1]; i++ {
			if lastAppeared[c[i]] != -1 {
				seg.UpdateAt(lastAppeared[c[i]], 0)
			}
			lastAppeared[c[i]] = i
			seg.UpdateAt(lastAppeared[c[i]], 1)
		}
		R = v[1]
		ans[v] = seg.GetRange(v[0], v[1])
	}
	for _, v := range lr {
		fmt.Println(ans[v])
	}
}

type SegmentTree struct {
	offset int
	data   []int
	inf    int
}

func InitSegmentTree(a []int, inf int) *SegmentTree {
	n := len(a)
	size := 1
	for size < n {
		size *= 2
	}
	data := make([]int, size*2)
	for j, i := 0, size-1; i < size+n-1; i++ {
		data[i] = a[j]
		j++
	}
	for i := size + n - 1; i < size*2; i++ {
		data[i] = 0
	}
	for i := size - 2; i >= 0; i-- {
		data[i] = data[i*2+1] + data[i*2+2]
	}
	return &SegmentTree{
		offset: size,
		data:   data,
		inf:    inf,
	}
}
func (tree *SegmentTree) GetRange(from, to int) int {
	return tree.getRange(from, to, 0, 0, tree.offset)
}
func (tree *SegmentTree) getRange(from, to, index, left, right int) int {
	if to <= left || right <= from {
		return tree.inf
	}
	if from <= left && right <= to {
		return tree.data[index]
	}
	med := (left + right) / 2
	lvalue := tree.getRange(from, to, index*2+1, left, med)
	rvalue := tree.getRange(from, to, index*2+2, med, right)
	return rvalue + lvalue
}
func (tree *SegmentTree) UpdateAt(index, value int) {
	idx := tree.offset - 1 + index
	tree.data[idx] = value
	for idx >= 1 {
		parent := (idx - 1) / 2
		left := parent*2 + 1
		right := parent*2 + 2
		tree.data[parent] = tree.data[left] + tree.data[right]
		idx = parent
	}
}


Measured memory_bytes: 98492