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_li, b_li+1, ..., b_ri. You are given the sequence b and all questions. Help Jeff, answer all his questions.

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.

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