You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Misaki Mei 给了你一个序列 $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
3
10

样例 $2$

见下发 $\textit{ex\_end2.in/ans}$。

该样例满足测试点 $2$ 的性质。

数据范围

对所有数据 $1\leq a_i\leq n$，$1\leq n\leq 5\times 10^5$。