Jeff and Removing Periods

## 题意 假如有一个长度为$n$ 的数列$a_1,a_2,\ldots,a_n$ 你允许对它进行操作，操作如下： 首先选择三个整数$v,t,k$ ，满足$a_v=a_{v+t}=a_{v+2t}=\ldots=a_{v+kt}$ 然后将其删除，可以得到一个新的数列。你能将新数列重排。 现有一个长度为$m$ 的数列，$q$ 个询问，每次询问$[l,r]$ 表示要你通过上面的操作将$[l,r]$ 的数删除的最小步数。 ## 数据范围 $m,q,a_i \le 10^5$ ## 输入 第一行包含一个整数$m$ ,接下来一行$m$ 个整数分别是$a_1,a_2,\ldots,a_m$ ，第三行是一个整数$q$ ,表示$q$ 组询问，接下来$q$ 行，每行两个数$l,r(l\leq\;r)$ ,表示询问的区间. ## 输出 $q$ 行表示每组询问的答案。 translated by Youngsc

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+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_{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_{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^{5}) $ . The next line contains $ m $ integers $ b_{1} $ , $ b_{2} $ , $ ... $ , $ b_{m} $ $ (1<=b_{i}<=10^{5}) $ . The third line contains integer $ q $ $ (1<=q<=10^{5}) $ — 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.

5
2 2 1 1 2
5
1 5
1 1
2 2
1 3
2 3

2
1
1
2
2

10
2 1 3 3 3 3 1 3 1 1
10
4 8
2 10
1 10
4 4
1 3
2 4
6 7
1 9
2 5
1 1

2
3
3
1
3
2
2
3
2
1