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
            
n = int(input())

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

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)]

res = [-1] * q

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    queries[l].append((r, i))
    
curr = FenwickTree([0] * (n + 1))
    
for i in range(n):
    for l in adds[i]:
        curr.update(l, 1)
    for l, pos in queries[i]:
        res[pos] = curr.query(l + 1)
    for l in dels[i]:
        curr.update(l, -1)

print(*res)