```go
package main

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

type P struct {
	v, m int
}

type Q struct {
	l, r, idx int
}

type Fenwick struct {
	t []int
	n int
}

func NewFenwick(nn int) *Fenwick {
	return &Fenwick{make([]int, nn+2), nn}
}

func (f *Fenwick) Update(idx, val int) {
	for idx <= f.n {
		f.t[idx] += val
		idx += idx & -idx
	}
}

func (f *Fenwick) Prefix(upto int) int {
	res := 0
	for upto > 0 {
		res += f.t[upto]
		upto -= upto & -upto
	}
	return res
}

func (f *Fenwick) Sum(lo, hi int) int {
	return f.Prefix(hi) - f.Prefix(lo-1)
}

var tree [][]int

func build(node, start, end int, a []int) {
	if start == end {
		tree[node] = []int{a[start]}
		return
	}
	mid := (start + end) / 2
	build(2*node, start, mid, a)
	build(2*node+1, mid+1, end, a)
	left := tree[2*node]
	right := tree[2*node+1]
	merged := make([]int, len(left)+len(right))
	i, j, k := 0, 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			merged[k] = left[i]
			i++
		} else {
			merged[k] = right[j]
			j++
		}
		k++
	}
	copy(merged[k:], left[i:])
	k += len(left) - i
	copy(merged[k:], right[j:])
	tree[node] = merged
}

func query(node, start, end, ql, qr int, lists *[]*[]int) {
	if ql > end || qr < start {
		return
	}
	if ql <= start && end <= qr {
		*lists = append(*lists, &tree[node])
		return
	}
	mid := (start + end) / 2
	query(2*node, start, mid, ql, qr, lists)
	query(2*node+1, mid+1, end, ql, qr, lists)
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, q int
	fmt.Fscan(in, &n, &q)
	a := make([]int, n+2)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &a[i])
	}
	pos := make([][]int, n+2)
	for i := 1; i <= n; i++ {
		pos[a[i]] = append(pos[a[i]], i)
	}
	tree = make([][]int, 4*(n+2))
	build(1, 1, n, a)
	var points []P
	for v := 1; v <= n; v++ {
		pv := pos[v]
		if len(pv) < 2 {
			continue
		}
		for ii := 0; ii < len(pv)-1; ii++ {
			le := pv[ii]
			ri := pv[ii+1]
			maxl := -1
			if le+1 <= ri-1 {
				var collected []*[]int
				query(1, 1, n, le+1, ri-1, &collected)
				for _, pp := range collected {
					list := *pp
					idx := sort.SearchInts(list, v)
					if idx > 0 {
						cand := list[idx-1]
						if cand > maxl {
							maxl = cand
						}
					}
				}
			}
			points = append(points, P{v, maxl})
		}
	}
	sort.Slice(points, func(i, j int) bool {
		return points[i].m < points[j].m
	})
	var queries []Q
	for qq := 0; qq < q; qq++ {
		var ll, rr int
		fmt.Fscan(in, &ll, &rr)
		queries = append(queries, Q{ll, rr, qq})
	}
	sort.Slice(queries, func(i, j int) bool {
		return queries[i].l < queries[j].l
	})
	prefix_count := make([]int, n+2)
	for i := 1; i <= n; i++ {
		prefix_count[i] = prefix_count[i-1] + len(pos[i])
	}
	ans := make([]int, q)
	ft := NewFenwick(n)
	curr := 0
	for qq := 0; qq < q; qq++ {
		ql := queries[qq].l
		qr := queries[qq].r
		qidx := queries[qq].idx
		lim := ql - 1
		for curr < len(points) && points[curr].m <= lim {
			ft.Update(points[curr].v, 1)
			curr++
		}
		ss := ft.Sum(ql, qr)
		kk := prefix_count[qr] - prefix_count[ql-1]
		ans[qidx] = kk - ss
	}
	out := bufio.NewWriter(os.Stdout)
	for i := 0; i < q; i++ {
		fmt.Fprintln(out, ans[i])
	}
	out.Flush()
}
```