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 DQuery {
	static class SegmentTree {
		public SegmentTree(int len) {
			//computeN(len);
			n = len;
			//tree = new int[n];
		}
		
		int N = 100011;  // limit for array size
		int n;  // array size
		int t[] = new int[2 * N];

		void build() {  // build the tree
		  for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
		}

		void modify(int p, int value) {  // set value at position p
		  for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
		}

		int query(int l, int r) {  // sum on interval [l, r)
		  int res = 0;
		  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		    if ((l&1) != 0) res += t[l++];
		    if ((r&1) != 0) res += t[--r];
		  }
		  return res;
		}
	}
	
	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 + 1);
			}
			else {
				if (idxs[queries.get(i).num] != 0) {
					segtree.modify(idxs[queries.get(i).num], 0);
				}
				segtree.modify(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;
	}
	
}