//In submission class declaration should be default not public
import java.util.*;
import java.io.*;
class D_query{
private static byte[] buf = new byte[1024];
private static int curChar;
private static int numChars;
private static SpaceCharFilter filter;
private static int[] count = new int[1111111];
private static int ans = 0;
private static int a[];
private static class Query{
int ind, l , r, an;
Query(int a,int b,int c){
ind = a;
l = b;
r = c;
an = 0;
}
}
private static void add(int p){
count[a[p]]++;
if(count[a[p]] == 1)
ans++;
}
private static void remove(int p){
if(count[a[p]] > 0){
count[a[p]]--;
if(count[a[p]] == 0)
ans--;
}
}
private static void soln(){
int n = nextInt();
a = nextIntArray(n);
int q = nextInt();
Query[] qu = new Query[q];
for (int i=0; i<q; i++) {
qu[i] = new Query(i,nextInt()-1,nextInt()-1);
}
Arrays.
sort(qu,
new Comparator
<Query
>(){ public int compare(Query q1,Query q2){
if((int)(q1.
l/Math.
sqrt(n
)) == (int)(q2.
l/Math.
sqrt(n
))) return q1.r - q2.r;
else
return (int)((int)q1.
l/Math.
sqrt(n
) - (int)q2.
l/Math.
sqrt(n
)); }
});
int curL = 0;
int curR = qu[0].l;
for (int i=0; i<q; i++) {
// System.out.println("asd " + i + " " + qu[i].l+ " " + qu[i].r);
// System.out.println("cur " + curL + " " + curR);
while(curL < qu[i].l){
remove(curL);
curL++;
}
// System.out.println("cur " + curL + " " + curR);
// System.out.println(Arrays.toString(count));
while(curL > qu[i].l){
add(curL-1);
curL--;
}
// System.out.println("cur " + curL + " " + curR);
// System.out.println(Arrays.toString(count));
while(curR <= qu[i].r){
add(curR);
curR++;
}
// System.out.println("cur " + curL + " " + curR);
// System.out.println(Arrays.toString(count));
while(curR > qu[i].r+1){
remove(curR-1);
curR--;
}
// System.out.println("cur " + curL + " " + curR);
// System.out.println(Arrays.toString(count));
// System.out.println(ans);
qu[i].an = ans;
}
Arrays.
sort(qu,
new Comparator
<Query
>(){ public int compare(Query q1,Query q2){
return q1.ind - q2.ind;
}
});
for (int i=0; i<q; i++) {
pw.println(qu[i].an);
}
}
public static void main
(String[] args
){ soln();
pw.close();
}
// To Get Input
// Some Buffer Methods
stream = stream1;
}
private static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private static boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
private static int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
private static int nextInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
private static long nextLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
private static String nextToken
() { int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
private static String nextLine
() { int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
private static int[] nextIntArray(int n) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = nextInt();
}
return arr;
}
private static long[] nextLongArray(int n) {
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = nextLong();
}
return arr;
}
private static void pArray(int[] arr){
for (int i=0; i<arr.length; i++) {
System.
out.
print(arr
[i
] + " "); }
return;
}
private static void pArray(long[] arr){
for (int i=0; i<arr.length; i++) {
System.
out.
print(arr
[i
] + " "); }
return;
}
private static boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return isWhitespace(c);
}
private interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}