B"Cosider a sequence, consisting of n integers: a1, a2, ..., an. Jeff can perform the following operation on 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, xe2 x80 x89ri. The answer to the question is the beauty of sequence bli, bli xe2 x80 x89+ xe2 x80 x891, ..., bri. You are given the sequence b and all questions. Help Jeff, answer all his questions. The first line contains integer m (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89m xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105). The next line contains m integers b1, b2, ..., bm (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89bi xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105). The third line contains integer q (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89q xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105) -- the number of questions. The next q lines contain pairs of integers, i-th of them contains a pair of integers li, ri (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89li xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ri xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89m) -- 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."...