鼹鼠又饿了。他发现了一个蚁群,由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. 鼹鼠吃掉蚂蚁 .