Yaroslav 有一个数组 p = p1, p2, ..., pn (1 ≤ pi ≤ n),由 n 个不同的整数组成。另外,他还有m个疑问:
- 查询号 i 表示为一对整数 li, ri (1 ≤ li ≤ ri ≤ n)。
- 查询 li, ri 的答案是整数对 q, w (li ≤ q, w ≤ ri) 的数量,使得 pq 是 pw 的除数。
帮助雅罗斯拉夫,回答他所有的疑问。
输入
第一行包含整数 n 和 m (1 ≤ n, m ≤ 2·105)。第二行包含 n 个不同的整数 p1, p2, ..., pn (1 ≤ pi ≤ n)。以下 m 行包含 Yaroslav 的查询。第 i 行包含整数 li, ri (1 ≤ li ≤ ri ≤ n)。
输出
打印 m 个整数 — 按照 Yaroslav 查询在输入中出现的顺序给出答案。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
1 1 1 1 1
输出 #1
1
输入 #2
10 9 1 2 3 4 5 6 7 8 9 10 1 10 2 9 3 8 4 7 5 6 2 2 9 10 5 10 4 10
输出 #2
27 14 8 4 2 1 2 7 9