#!/bin/python3

import os
import sys
import math
import bisect
from collections import defaultdict

t = []
query_solutions = [0]*1000001
query_array = []
last_pos = [-1]*1000001
prev_last_pos = [-1]*1000001
bin_tree = [0]*1000001

def preprocess(n):
    D = {}
    counter = 0
    for i in range(n):
        if t[i] in D:
            t[i] = D[t[i]]
        else:
            D[t[i]] = counter
            t[i] = counter
            counter += 1

def update_bin_tree(n, ind, val):

    while ind <= n:
        bin_tree[ind] += val
        ind += ind & (-ind)

def get_query(ind):
    sol = 0

    while ind > 0:
        sol += bin_tree[ind]
        ind -= ind & (-ind)

    return sol


def compute(n, q):

    q_count = 0
    for i in range(n):

        #process the array up to index i
        if last_pos[t[i]] != -1:
            #push a -2 into last_pos
            update_bin_tree(n, last_pos[t[i]]+1, -2)

            #check for prev_last_pos
            if prev_last_pos[t[i]] != -1:
                #push a 1 into prev_last_pos
                update_bin_tree(n, prev_last_pos[t[i]]+1, 1)

            #update prev_last_pos
            prev_last_pos[t[i]] = last_pos[t[i]]

        #update last_pos
        last_pos[t[i]] = i
        update_bin_tree(n, i+1, 1)

        while (q_count < q) and (query_array[q_count][0] == i):

            query_solutions[query_array[q_count][2]] = get_query(i+1) - get_query(query_array[q_count][1])
            q_count += 1


if __name__ == '__main__':
    n = int(input())

    t = list(map(int, input().rstrip().split()))

    preprocess(n)
    q = int(input())

    for i in range(q):
        l, r = [int(x) - 1 for x in input().split()]
        Q = (r, l, i)
        query_array.append(Q)

    query_array.sort()
    compute(n, q)

    for i in range(q):
        print(query_solutions[i])
    #print(bin_tree)