import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
	
 
	static class SegmentTree {
 
		int tree[];
		int n;
 
		public SegmentTree(int len) {
			computeN(len);
			tree = new int[n];
		}
 
		int query(int i, int j) {
			return query(1, 1, n / 2, i, j);
		}
		
		int query(int node, int l, int r, int i, int j) {
			if (node > n || node < 1 || r < l || l < 1 || r > n / 2 || r < i || l > j)
				return 0;
			if (l >= i && r <= j) {
				return tree[node];
			}
			int mid = (l + r) >> 1;
			int left = node << 1;
			int right = left | 1;
			int lf = query(left, l, mid, i, j);
			int ri = query(right, mid + 1, r, i , j);
			return lf + ri;
		}
		
		void update(int i, int j, int val) {
			update(1, 1, n / 2, i, j, val);
		}
		
		int update(int node, int l, int r, int i, int j, int val) {
			if (node > n || node < 1 || r < l || l < 1 || r > n / 2)
				return 0;
			if (l >= i && r <= j) {
				//System.out.println("I am putting " + val);
				return tree[node] = val;
			}
			if (r < i || l > j) {
				return tree[node];
			}
			int mid = (l + r) >> 1;
			int left = node << 1;
			int right = left | 1;
			int lf = update(left, l, mid, i, j, val);
			int ri = update(right, mid + 1, r, i , j, val);
			return tree[node] = lf + ri;
		}
 
		void computeN(int x) {
			n = 1;
			while (n < x)
				n <<= 1;
			n <<= 1;
		}
	}
	
	static class Query implements Comparable<Query> {
		int left, right, num, idx;
		boolean query;
		public Query(int l, int r, int n, int i, boolean q) {
			left = l;
			right = r;
			num = n;
			idx = i;
			query = q;
		}
		@Override
		public int compareTo(Query o) {
			// TODO Auto-generated method stub
			if (right == o.right)
				if (query == o.query)
					return 0;
				else
					if (!query && o.query)
						return -1;
					else
						return 1;
			else 
				if (right < o.right)
					return -1;
				else
					return 1;
		}
	}
	
	public static void main(String[] args) throws Exception {
		PrintWriter out = new PrintWriter(System.out);
		int n = next_int();
		SegmentTree segtree = new SegmentTree(n);
		ArrayList<Query> queries = new ArrayList<Query>(1);
		for (int i = 0; i < n; i++) {
			int x = next_int();
			queries.add(new Query(1, i + 1, x, i, false));
		}
		int q = next_int();
		for (int i = 0; i < q; i++) {
			int l = next_int();
			int r = next_int();
			queries.add(new Query(l, r, 0, i, true));
		}
		Collections.sort(queries);
		int idxs[] = new int[1000001];
		int qans[] = new int[q];
		for (int i = 0; i < n + q; i++) {
			if (queries.get(i).query) {
				qans[queries.get(i).idx] = segtree.query(queries.get(i).left, queries.get(i).right);
			}
			else {
				if (idxs[queries.get(i).num] != 0) {
					segtree.update(idxs[queries.get(i).num], idxs[queries.get(i).num], 0);
				}
				segtree.update(queries.get(i).right, queries.get(i).right, 1);
				idxs[queries.get(i).num] = queries.get(i).right;
			}
		}
		for (int i = 0; i < q; i++) {
			out.println(qans[i]);
		}
		out.flush();
		out.close();
	}
	
	
	static int index, size;
	static byte[] b = new byte[1024];
 
	static byte next_byte() throws Exception {
		if (index == size) {
			index = 0;
			size = System.in.read(b);
		}
		return b[index++];
	}
 
	static int next_int() throws Exception {
		int n = 0;
		byte c = next_byte();
		while (!('0' <= c && c <= '9')) {
			c = next_byte();
		}
		while ('0' <= c && c <= '9') {
			n = n * 10 + c - '0';
			c = next_byte();
		}
		return n;
	}
	
}