[Ynoi2018]GOSICK

题目背景

![](https://cdn.luogu.com.cn/upload/pic/58864.png) 洋...娃娃? “终于来了啊” “太慢了,伴随春天而来的死神” ![](https://cdn.luogu.com.cn/upload/pic/58865.png) 维多利...加? 你...手不疼吗 手通红的啊 “无路赛...振作一点” “如果在这里放弃的话就永远绝交了,久城!” “要一起回去” “之前也说过的吧 一起...” “我们俩分离的地方,不是这里吧” ![](https://cdn.luogu.com.cn/upload/pic/58866.png) “太慢了,伴随春天而来的死神” 别生气嘛 我这也是很赶时间了 信收到了吗 “嗯,因为都很认真写上地址了” “运用智慧之泉,终于到达了这里” ![](https://cdn.luogu.com.cn/upload/pic/58867.png) 无论世界如何改变 这次之后 将再不分离

题目描述

维多利加给了你一个序列 $a$,每次询问给一个区间 $[l,r]$。 查询 $l \leq i,j\leq r$,且 $a_i$ 是 $a_j$ 倍数的二元组 $(i,j)$ 的个数。

输入输出格式

输入格式


第一行两个整数表示 $n,m$。 第二行 $n$ 个整数表示序列 $a$。 之后 $m$ 行,每行两个整数 $l,r$ 表示一次询问。

输出格式


对于每个询问,输出一行一个整数表示答案。

输入输出样例

输入样例 #1

6 3
1 1 4 5 1 4
1 1
4 5
1 4

输出样例 #1

1
3
10

说明

Idea:nzhtl1477,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477 对于 $100\%$ 的数据,$1\leq n,m,a_i\leq 5\times 10^5$,$1\leq l\leq r\leq n$。