D. Ярослав и делители
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Ярослава есть массив 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 строках заданы запросы Ярослава. В i-той строке записаны целые числа li, ri (1 ≤ li ≤ ri ≤ n).

Выходные данные

Выведите m целых чисел — ответы на запросы Ярослава в порядке их следования во входных данных.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
1 1
1
1 1
Выходные данные
1
Входные данные
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
Выходные данные
27
14
8
4
2
1
2
7
9