CF351D.Jeff and Removing Periods

Cosider 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 + 2_t_, ..., 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__l__i, b__l__i + 1, ..., b__r__i. You are given the sequence b and all questions. Help Jeff, answer all his questions.

考虑一个由 $n$ 个整数组成的序列：$a_1, a_2, \dots, a_n$。Jeff 可以对序列 $a$ 执行如下操作：

• 选取三个整数 $v$、$t$、$k$（满足 $1 \le v, t \le n$；$0 \le k$；且 $v + tk \le n$），使得
  $a_v = a_{v+t},\; a_{v+t} = a_{v+2t},\; \dots,\; a_{v+t(k-1)} = a_{v+tk}$；
• 从序列 $a$ 中删除元素 $a_v, a_{v+t}, \dots, a_{v+tk}$，剩余元素需重新编号为 $a_1, a_2, \dots, a_{n-k-1}$；
• 将序列 $a$ 中剩余的元素以任意顺序重新排列。

序列 $a$ 的**优美值（beauty）**定义为：将序列 $a$ 中所有元素全部删除所需的最少操作次数。

Jeff 已写下长度为 $m$ 的整数序列 $b_1, b_2, \dots, b_m$。现在他要提出 $q$ 个询问，每个询问由两个整数 $l_i, r_i$ 描述。该询问的答案即为子序列 $b_{l_i}, b_{l_i+1}, \dots, b_{r_i}$ 的优美值。
已知序列 $b$ 及所有询问，请帮助 Jeff 回答全部询问。

The first line contains integer m (1 ≤ m ≤ 105). The next line contains m integers _b_1, _b_2, ..., b__m (1 ≤ b__i ≤ 105).

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

第一行包含一个整数 $m$（$1 \leq m \leq 10^5$）。第二行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \leq b_i \leq 10^5$）。

第三行包含一个整数 $q$（$1 \leq q \leq 10^5$）—— 问题的数量。接下来的 $q$ 行每行包含一对整数，其中第 $i$ 行包含一对整数 $l_i, r_i$（$1 \leq l_i \leq r_i \leq m$）—— 描述第 $i$ 个问题。

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

在 q 行中输出 Jeff 的查询结果。请按照输入中问题的顺序输出答案。