Cosider a sequence, consisting of n integers: a1, a2, ..., an. Jeff can perform the following operation on sequence a:

  * take three integers v, t, k (1 ≤ v, t ≤ n; 0 ≤ k; v + tk ≤ n), such that av = av + t, av + t = av + 2t, ..., av + t(k - 1) = av + tk; 
  * remove elements av, av + t, ..., av + t·k from the sequence a, the remaining elements should be reindexed a1, a2, ..., an - k - 1. 
  * permute in some order the remaining elements of sequence a. 



A beauty of a sequence a is the minimum number of operations that is needed to delete all elements from sequence a.

Jeff's written down a sequence of m integers b1, b2, ..., bm. Now he wants to ask q questions. Each question can be described with two integers li, ri. The answer to the question is the beauty of sequence bli, bli + 1, ..., bri. You are given the sequence b and all questions. Help Jeff, answer all his questions.

Input

The first line contains integer m (1 ≤ m ≤ 105). The next line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 105). 

The third line contains integer q (1 ≤ q ≤ 105) — the number of questions. The next q lines contain pairs of integers, i-th of them contains a pair of integers li, ri (1 ≤ li ≤ ri ≤ m) — the description of i-th question.

Output

In q lines print the answers to Jeff's queries. Print the answers according to the order of questions in input.

Examples

Input

5
2 2 1 1 2
5
1 5
1 1
2 2
1 3
2 3


Output

2
1
1
2
2


Input

10
2 1 3 3 3 3 1 3 1 1
10
4 8
2 10
1 10
4 4
1 3
2 4
6 7
1 9
2 5
1 1


Output

2
3
3
1
3
2
2
3
2
1


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

// n sq(n) offline soln using mo http://codeforces.com/blog/entry/7383
public class JeffAndRemovingPeriodsMo {
	static int N;
	static int[] arr;
	static int Q;
	static Interval[] queries;
	static int MAX = 100005;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		StringTokenizer tk;

		N = Integer.parseInt(in.readLine());
		arr = new int[N + 1];
		tk = tk(in.readLine());
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(tk.nextToken());
		}

		Q = Integer.parseInt(in.readLine());
		queries = new Interval[Q];
		for (int i = 0; i < Q; i++) {
			tk = tk(in.readLine());
			queries[i] = new Interval(i, Integer.parseInt(tk.nextToken()),
					Integer.parseInt(tk.nextToken()));
		}


		int[] ans = new int[Q];
		final int BUCKET = (int) Math.sqrt(N);
		// solve count distinct using mo
		Arrays.sort(queries, new Comparator<Interval>() {
			@Override
			public int compare(Interval o1, Interval o2) {
				int dif = o1.l / BUCKET - o2.l/BUCKET;
				if(dif != 0) return dif;
				return o1.r - o2.r;
			}
		});
		
		int l = 1;
		int r = 1;
		int[] tally = new int[MAX];
		int num = 1;
		tally[arr[l]]++;
		for(Interval query : queries) {
			while(l > query.l) {
				l--;
				tally[arr[l]]++;
				if(tally[arr[l]] == 1){
					num++;
				}
			}
			
			while(r < query.r) {
				r++;
				tally[arr[r]]++;
				if(tally[arr[r]] == 1){
					num++;
				}
			}
			
			while(l < query.l) {
				tally[arr[l]]--;
				if(tally[arr[l]] == 0){
					num--;
				}
				l++;
			}
			
			while(r > query.r) {
				tally[arr[r]]--;
				if(tally[arr[r]] == 0){
					num--;
				}
				r--;
			}
			ans[query.id] = num;
		}
		
		// solve arith - solved before, too lazy to recode :D

		Arrays.sort(queries, new Comparator<Interval>() {
			@Override
			public int compare(Interval o1, Interval o2) {
				return o1.r - o2.r;
			}
		});
		
		// an element is good up until he is no longer arith spaced from the right
		// make a[i] = 1 for that element always, then put -1 on the left the moment it is no longer good
		Fenwick1 fen2 = new Fenwick1(N);
		int curr = 0;
		// one indexed. 0 means none yet
		int[] prev = new int[MAX];
		int[] pprev = new int[MAX];
		// 0 means no period yet
		int[] period = new int[MAX];
		// index for which the element's arith is broken
		int[] bad = new int[MAX];
		for (Interval query : queries) {
			if (query.r != curr) {
				while (curr < query.r) {
					curr++;
					int el = arr[curr];
					
					if(prev[el] > 0) {
						int newperiod = curr - prev[el] + 1;
						// reset the good point back to 0
						fen2.increment(prev[el], -1);
						if(period[el] == newperiod) {
							// don't change last bad stopping point, it's still the same
						} else {
							period[el] = newperiod;
							if(bad[el] != 0) {
								// set the previous bad back to 0
								fen2.increment(bad[el], 1);
							}
							// make a new bad
							bad[el] = pprev[el];
							if(bad[el] != 0)
								fen2.increment(bad[el], -1);
						}
					}
					
					fen2.increment(curr, 1);
					pprev[el] = prev[el];
					prev[el] = curr;
				}
			}
			if(fen2.getTotalFreq(query.r) - fen2.getTotalFreq(query.l - 1) == 0) {
				ans[query.id]++;
			}
		}

		for (int qid = 0; qid < Q; qid++) {
			out.println(ans[qid]);
		}

		out.close();
	}
	
	static class Fenwick1 {
		int[] tree;

		public Fenwick1(int n) {
			tree = new int[n + 1];
		}

		public void increment(int i, int val) {
			while (i < tree.length) {
				tree[i] += val;
				i += (i & -i);
			}
		}

		public int getTotalFreq(int i) {
			int sum = 0;
			while (i > 0) {
				sum += tree[i];
				i -= (i & -i);
			}
			return sum;
		}
	}

	static class Interval {
		public int l;
		public int r;
		public int id;

		public Interval(int id, int l, int r) {
			this.id = id;
			this.l = l;
			this.r = r;
		}
	}

	static StringTokenizer tk(String s) {
		return new StringTokenizer(s);
	}
}
