package main

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

func add(tree []int, i int, delta int) {
	for ; i < len(tree); i += i & -i {
		tree[i] += delta
	}
}

func query(tree []int, i int) int {
	sum := 0
	for ; i > 0; i -= i & -i {
		sum += tree[i]
	}
	return sum
}

type Query struct {
	L, R, id int
}

func readInt(reader *bufio.Reader) int {
	var res int
	b, err := reader.ReadByte()
	for err == nil && (b < '0' || b > '9') {
		b, err = reader.ReadByte()
	}
	if err != nil {
		return 0
	}
	for err == nil && b >= '0' && b <= '9' {
		res = res*10 + int(b-'0')
		b, err = reader.ReadByte()
	}
	return res
}

func main() {
	reader := bufio.NewReaderSize(os.Stdin, 4*1024*1024)
	m := readInt(reader)
	if m == 0 {
		return
	}

	b := make([]int, m+1)
	maxVal := 0
	for i := 1; i <= m; i++ {
		b[i] = readInt(reader)
		if b[i] > maxVal {
			maxVal = b[i]
		}
	}

	pos := make([][]int, maxVal+1)
	for i := 1; i <= m; i++ {
		pos[b[i]] = append(pos[b[i]], i)
	}

	violating_R := make([]int, m+1)
	for i := 1; i <= m; i++ {
		violating_R[i] = m + 1
	}

	for x := 1; x <= maxVal; x++ {
		p := pos[x]
		if len(p) < 3 {
			continue
		}
		for i := 0; i < len(p)-2; i++ {
			if p[i+1]-p[i] != p[i+2]-p[i+1] {
				violating_R[p[i]] = p[i+2]
			}
		}
	}

	q := readInt(reader)
	queries := make([]Query, q)
	for i := 0; i < q; i++ {
		queries[i] = Query{
			L:  readInt(reader),
			R:  readInt(reader),
			id: i,
		}
	}

	sort.Slice(queries, func(i, j int) bool {
		return queries[i].L > queries[j].L
	})

	treeD := make([]int, m+2)
	treeB := make([]int, m+2)

	first := make([]int, maxVal+1)
	min_R := make([]int, maxVal+1)
	for i := 0; i <= maxVal; i++ {
		first[i] = m + 1
		min_R[i] = m + 1
	}

	ans := make([]int, q)
	currL := m

	for _, qry := range queries {
		for currL >= qry.L {
			l := currL
			x := b[l]

			if first[x] <= m {
				add(treeD, first[x], -1)
			}
			first[x] = l
			add(treeD, first[x], 1)

			if violating_R[l] <= m {
				if min_R[x] <= m {
					add(treeB, min_R[x], -1)
				}
				min_R[x] = violating_R[l]
				add(treeB, min_R[x], 1)
			}

			currL--
		}

		D := query(treeD, qry.R)
		B := query(treeB, qry.R)
		if B < D {
			ans[qry.id] = D
		} else {
			ans[qry.id] = D + 1
		}
	}

	writer := bufio.NewWriterSize(os.Stdout, 4*1024*1024)
	for i := 0; i < q; i++ {
		fmt.Fprintln(writer, ans[i])
	}
	writer.Flush()
}