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))
aW1wb3J0IHN5cwppbXBvcnQgb3MsaW8KaW5wdXQ9aW8uQnl0ZXNJTyhvcy5yZWFkKDAsb3MuZnN0YXQoMCkuc3Rfc2l6ZSkpLnJlYWRsaW5lCgpuID0gaW50KGlucHV0KCkpCmFyciA9IGxpc3QobWFwKGludCwgaW5wdXQoKS5zcGxpdCgpKSkKc3FyID0gaW50KG4qKjAuNSkKbSA9IGludChpbnB1dCgpKQpxdWVyeSA9IFtdCmZvciBpIGluIHJhbmdlKG0pOgogICAgYSwgYiA9IG1hcChpbnQsIGlucHV0KCkuc3BsaXQoKSkKICAgIHF1ZXJ5LmFwcGVuZCgoYS0xLCBiLTEsIGkpKQpxdWVyeS5zb3J0KGtleT1sYW1iZGEgeDogKHhbMF0vL3NxciwgeFsxXSkpCgpsLCByID0gMCwgLTEKY291bnQgPSAwCmQgPSBbMF0gKiAxMDAwMDAwCnJlc3VsdCA9IFswXSAqIG0KZm9yIGEsIGIsIGkgaW4gcXVlcnk6CiAgICB3aGlsZSBsID4gYToKICAgICAgICBsIC09IDEKICAgICAgICBpZiBkW2FycltsXV0gPT0gMDoKICAgICAgICAgICAgY291bnQgKz0gMQogICAgICAgIGRbYXJyW2xdXSArPSAxCiAgICAgICAgCiAgICB3aGlsZSByIDwgYjoKICAgICAgICByICs9IDEKICAgICAgICBpZiBkW2FycltyXV0gPT0gMDoKICAgICAgICAgICAgY291bnQgKz0gMQogICAgICAgIGRbYXJyW3JdXSArPSAxCiAgICAgICAgCiAgICB3aGlsZSBsIDwgYToKICAgICAgICBkW2FycltsXV0gLT0gMQogICAgICAgIGlmIGRbYXJyW2xdXSA9PSAwOgogICAgICAgICAgICBjb3VudCAtPSAxCiAgICAgICAgbCArPSAxCiAgICAgICAgCiAgICB3aGlsZSByID4gYjoKICAgICAgICBkW2FycltyXV0gLT0gMQogICAgICAgIGlmIGRbYXJyW3JdXSA9PSAwOgogICAgICAgICAgICBjb3VudCAtPSAxCiAgICAgICAgciAtPSAxCiAKICAgIHJlc3VsdFtpXSA9IHN0cihjb3VudCkKICAgIApwcmludCgiXG4iLmpvaW4ocmVzdWx0KSk=