Cosider a sequence, consisting of n integers: a₁, a₂, ..., 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₁, a₂, ..., 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₁, b₂, ..., 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_{l_i}, b_{l_i + 1}, ..., b_{r_i}. 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⁵). The next line contains m integers b₁, b₂, ..., b_m (1 ≤ b_i ≤ 10⁵).

The third line contains integer q (1 ≤ q ≤ 10⁵) — 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.

Jeff and Removing Periods

Examples