from collections import defaultdict

class FenwickTree:
    def __init__(self, x):
        self.bit = x
        for i in range(len(x)):
            j = i | (i + 1)
            if j < len(x):
                x[j] += x[i]

    def update(self, idx, x):
        while idx < len(self.bit):
            self.bit[idx] += x
            idx |= idx + 1

    def query(self, end):
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x

class Seg:
    def __init__(self, n):
        N = 1
        while N < n:
            N <<= 1
        self.N = N
        self.t = [-1] * (2 * N)

    def set(self, i, v):
        i += self.N
        self.t[i] = v
        i //= 2
        while i:
            a = self.t[2 * i]
            b = self.t[2 * i + 1]
            self.t[i] = a if a > b else b
            i //= 2

    def prefmax(self, r):
        l = self.N
        r = r + self.N + 1
        res = -1
        while l < r:
            if l & 1:
                v = self.t[l]
                if v > res: res = v
                l += 1
            if r & 1:
                r -= 1
                v = self.t[r]
                if v > res: res = v
            l //= 2
            r //= 2
        return res

n = int(input())
arr = list(map(int, input().split()))

pos = defaultdict(list)
for i, v in enumerate(arr):
    pos[v].append(i)

ok = [-1] * n
for v, lst in pos.items():
    m = len(lst)
    if m == 1:
        ok[lst[0]] = n - 1
        continue
    d = [lst[i + 1] - lst[i] for i in range(m - 1)]
    r = [0] * (m - 1)
    r[m - 2] = m - 2
    for i in range(m - 3, -1, -1):
        if d[i] == d[i + 1]:
            r[i] = r[i + 1]
        else:
            r[i] = i
    for t in range(m):
        if t == m - 1:
            reach_idx = t
        else:
            reach_idx = r[t] + 1
        if reach_idx + 1 < m:
            nxt = lst[reach_idx + 1]
        else:
            nxt = n
        ok[lst[t]] = nxt - 1

adds = [[] for _ in range(n)]
dels = [[] for _ in range(n)]
prev = {}
for i in range(n):
    adds[prev.get(arr[i], -1) + 1].append(i)
    dels[i].append(i)
    prev[arr[i]] = i

q = int(input())
queries = [[] for _ in range(n)]
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    queries[l].append((r, i))

bit = FenwickTree([0] * (n + 1))
seg = Seg(n)
res = [0] * q

for i in range(n):
    for p in adds[i]:
        bit.update(p, 1)
        seg.set(p, ok[p])
    for r, idx in queries[i]:
        distinct = bit.query(r + 1)
        pm = seg.prefmax(r)
        add = 0 if pm >= r else 1
        res[idx] = distinct + add
    for p in dels[i]:
        bit.update(p, -1)
        seg.set(p, -1)

print("\n".join(map(str, res)))