import sys
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n = int(input())
arr = list(map(int, input().split()))
sqr = int(n**0.5)
m = int(input())
query = []
for i in range(m):
    a, b = map(int, input().split())
    query.append((a-1, b-1, i))
query.sort(key=lambda x: (x[0]//sqr, x[1]))

l, r = 0, -1
count = 0
d = [0] * 1000000
result = [0] * m
for a, b, i in query:
    while l > a:
        l -= 1
        if d[arr[l]] == 0:
            count += 1
        d[arr[l]] += 1
        
    while r < b:
        r += 1
        if d[arr[r]] == 0:
            count += 1
        d[arr[r]] += 1
        
    while l < a:
        d[arr[l]] -= 1
        if d[arr[l]] == 0:
            count -= 1
        l += 1
        
    while r > b:
        d[arr[r]] -= 1
        if d[arr[r]] == 0:
            count -= 1
        r -= 1
 
    result[i] = str(count)
    
print("\n".join(result))