← 返回题目列表

Codeforces · 474/F

F. 蚁群

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

鼹鼠又饿了。他发现了一个蚁群,由n只蚂蚁组成,排列成一排。每只蚂蚁 i (1 ≤ i ≤ n) 的强度为 si。

为了让他的晚餐变得更有趣,鼹鼠为蚂蚁们组织了一场“饥饿游戏”。他选择两个数字 l 和 r (1 ≤ l ≤ r ≤ n),每对指数在 l 和 r 之间(含)的蚂蚁将进行战斗。当两只蚂蚁 i 和 j 战斗时,只有当 si 除 sj 时,蚂蚁 i 才获得 1 个战斗点(同样,只有当 sj 除 si 时,蚂蚁 j 才获得 1 个战斗点)。

所有战斗结束后,鼹鼠获得排名。获得 vi 战斗点数的蚂蚁 i 只有在 vi = r - l 时才会被释放,换句话说,只有在它参加的每场战斗中都获得一分时,它才会被释放。之后,鼹鼠吃掉了剩下的蚂蚁。请注意,可能有很多蚂蚁被释放,甚至没有。

为了选择最佳序列,鼹鼠给你 t 个片段 [li, ri],并询问每个片段,如果这些蚂蚁打架,他会吃掉多少只蚂蚁。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105),即蚁群的大小。

第二行包含n个整数s1, s2, ..., sn (1 ≤ si ≤ 109),即蚂蚁的强项。

第三行包含一个整数t (1 ≤ t ≤ 105),即测试用例的数量。

接下来的 t 行中的每一行都包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n),描述一个查询。

输出

打印到标准输出 t 行。第 i 行包含段 [li, ri] 中鼹鼠吃掉的蚂蚁数量。

示例

输入 #1

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

输出 #1

4
4
1
1

注意

在第一次测试中,每只蚂蚁的战斗点数为 v = [4, 0, 2, 0, 2],因此 1 号蚂蚁被释放。鼹鼠吃掉了蚂蚁 2、3、4、5。

在第二个测试用例中,战斗点为 v = [0, 2, 0, 2],因此没有蚂蚁被释放,所有蚂蚁都被鼹鼠吃掉了。

在第三个测试用例中,战斗点为 v = [2, 0, 2],因此 3 号和 5 号蚂蚁被释放。鼹鼠只吃蚂蚁 4.

在第四个测试用例中,战斗点为 v = [0, 1],因此 5 号蚂蚁被释放。 4. 鼹鼠吃掉蚂蚁 .