考虑一个由 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