← 返回题目列表

Codeforces · 351/D

D. 杰夫和删除句号

中文机器翻译题面 查看原题

考虑一个由 n 个整数组成的序列:a1, a2, ..., an。 Jeff可以对序列a执行以下操作:

- 取三个整数 v、t、k (1 ≤ v, t ≤ n; 0 ≤ k; v + tk ≤ n),使得 av = av + t,av + t = av + 2t, ..., av + t(k - 1) = av + tk;
- 从序列 a 中删除元素 av, av + t, ..., av + t·k,剩余元素应重新索引 a1, a2, ..., an - k - 1。
- 按某种顺序排列序列 a 的剩余元素。

序列 a 的优点在于删除序列 a 中的所有元素所需的操作次数最少。

Jeff 写下了 m 个整数 b1, b2, ..., bm 的序列。现在他想问q 个问题。每个问题都可以用两个整数li、ri 来描述。问题的答案是序列 bli, bli + 1, ..., bri 的美妙之处。给你序列 b 和所有问题。帮助杰夫,回答他所有的问题。

输入

第一行包含整数 m (1 ≤ m ≤ 105)。下一行包含 m 个整数 b1, b2, ..., bm (1 ≤ bi ≤ 105)。

第三行包含整数 q (1 ≤ q ≤ 105) — 问题数。接下来的 q 行包含整数对,其中第 i 行包含一对整数 li, ri (1 ≤ li ≤ ri ≤ m) — 第 i 个问题的描述。

输出

在 q 行中打印 Jeff 的查询的答案。根据输入问题的顺序打印答案。

示例

输入 #1

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

输出 #1

2
1
1
2
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

2
3
3
1
3
2
2
3
2
1