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 \le v,t \le n;0 \le k;v+tk \le n), such that av = av+t, av+t = av+2t, ..., av+t(k-1) = av+tk; remove elements av, av+t, ..., av+t \cdot 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.

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

The third line contains integer q (1 \le q \le 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 \le li \le ri \le 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.