Background

Yo... dolls?

“You finally came.”

“So slow, the reaper who comes with spring.”
Victo... rica?

You... doesn’t your hand hurt?

Your hand is all red.

“Urusai... pull yourself together.”

“If you give up here, then we will never talk again, Kujo!”

“We are going back together.”

“I told you before too, together...”

“The place where we part, isn’t here, right?”

“So slow, the reaper who comes with spring.”

Don’t be mad, I was in a real hurry too.

Did you receive the letter?

“Yeah, because the address was written very carefully.”

“Using the fountain of wisdom, we finally arrived here.”

No matter how the world changes,

After this time, we will never be separated again.

Problem Description

Victo rica gives you a sequence $a$. Each query gives an interval $[l,r]$.

Count the number of ordered pairs $(i,j)$ such that $l \leq i,j \leq r$ and $a_i$ is a multiple of $a_j$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers, representing the sequence $a$.

Then follow $m$ lines, each containing two integers $l,r$, representing one query.

Output Format

For each query, output one line with one integer, representing the answer.

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

1
3
10

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

Constraints: for $100\%$ of the data, $1 \leq n,m,a_i \leq 5 \times 10^5$, $1 \leq l \leq r \leq n$.

Translated by ChatGPT 5