'''
莫队算法暴力加速
'''

import sys
import math

n = int(input())
s = sys.stdin.readline()
arr = list(map(int, s.split()))

r = []
part_len = int(math.sqrt(n))

m = int(input())
ss = sys.stdin.readlines()

idx = 0
for s in ss:
    a, b = map(int, s.split())
    a, b = a-1, b-1
    r.append((a // part_len, b, a, idx)) # [段号, 右端点位置，左端点位置，询问序号]
    idx += 1

r.sort()
i, j = 0, 0           # 当前的左右边界
cnt = [0] * 1000005     # 每一个数值个数计数
cnt[arr[0]] = 1
ans = 1

ret = [0] * m
for _, b, a, idx in r:
    if i < a:
        while i != a:
            cnt[arr[i]] -= 1
            if cnt[arr[i]] == 0:
                ans -= 1
            i += 1

    elif i > a:
        while i != a:
            i -= 1
            cnt[arr[i]] += 1
            if cnt[arr[i]] == 1:
                ans += 1

    if j < b:
        while j != b:
            j += 1
            cnt[arr[j]] += 1
            if cnt[arr[j]] == 1:
                ans += 1
    elif j > b:
        while j != b:
            cnt[arr[j]] -= 1
            if cnt[arr[j]] == 0:
                ans -= 1
            j -= 1

    ret[idx] = ans

for ans in ret:
    print(ans)