Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Jeff and Removing Periods

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputCosider a sequence, consisting of *n* integers: *a*_{1}, *a*_{2}, ..., *a*_{n}. 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*a*_{v}=*a*_{v + t},*a*_{v + t}=*a*_{v + 2t}, ...,*a*_{v + t(k - 1)}=*a*_{v + tk}; - remove elements
*a*_{v},*a*_{v + t}, ...,*a*_{v + t·k}from the sequence*a*, the remaining elements should be reindexed*a*_{1},*a*_{2}, ...,*a*_{n - 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 *b*_{1}, *b*_{2}, ..., *b*_{m}. Now he wants to ask *q* questions. Each question can be described with two integers *l*_{i}, *r*_{i}. The answer to the question is the beauty of sequence *b*_{li}, *b*_{li + 1}, ..., *b*_{ri}. You are given the sequence *b* and all questions. Help Jeff, answer all his questions.

Input

The first line contains integer *m* (1 ≤ *m* ≤ 10^{5}). The next line contains *m* integers *b*_{1}, *b*_{2}, ..., *b*_{m} (1 ≤ *b*_{i} ≤ 10^{5}).

The third line contains integer *q* (1 ≤ *q* ≤ 10^{5}) — the number of questions. The next *q* lines contain pairs of integers, *i*-th of them contains a pair of integers *l*_{i}, *r*_{i} (1 ≤ *l*_{i} ≤ *r*_{i} ≤ *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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/25/2017 00:58:37 (p1).

Desktop version, switch to mobile version.
User lists

Name |
---|