Nobody is needed
Contest: Codeforces Round 936 (Div. 2)
Difficulty rating: 2500
Tags: 2-sat, data structures, dfs and similar, dp

Oleg received a permutation $$$a$$$ of length $$$n$$$ as a birthday present.

Oleg's friend Nechipor asks Oleg $$$q$$$ questions, each question is characterized by two numbers $$$l$$$ and $$$r$$$, in response to the question Oleg must say the number of sets of indices $$$(t_1, t_2, \ldots, t_k)$$$ of any length $$$k \ge 1$$$ such that:

- $$$l \le t_i \le r$$$ for each $$$i$$$ from $$$1$$$ to $$$k$$$.
- $$$t_i < t_{i+1}$$$ for each $$$i$$$ from $$$1$$$ to $$$k-1$$$.
- $$$a_{t_{i+1}}$$$ is divisible by $$$a_{t_i}$$$ for each $$$i$$$ from $$$1$$$ to $$$k-1$$$.

Help Oleg and answer all of Nechipor's questions.

Input format:
Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of sets of input data. The description of the sets of input data follows.

The first line of each set of input data contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — the length of the permutation and the number of Nechipor's questions.

The second line of each set of input data contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the permutation $$$a$$$ itself.

In each of the next $$$q$$$ lines of each set of input data, there are two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the next question of Nechipor.

It is guaranteed that the sum of the values of $$$n$$$ and the sum of the values of $$$q$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each set of input data, output the answers to all of Nechipor's questions.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
All suitable arrays in the first set of input data: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 3$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 6, 7$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 5$$$), ($$$2, 6$$$), ($$$2, 7$$$), ($$$2, 8$$$), ($$$2, 6, 7$$$), ($$$6, 7$$$).

All suitable arrays in the fourth set of input data: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 2$$$), ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 5$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 8$$$), ($$$1, 2, 4$$$), ($$$1, 2, 6$$$), ($$$1, 2, 8$$$), ($$$1, 2, 4, 8$$$), ($$$1, 3, 6$$$), ($$$1, 4, 8$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$2, 8$$$), ($$$2, 4, 8$$$), ($$$3, 6$$$), ($$$4, 8$$$).

Example input:
4
8 8
2 1 6 3 5 4 8 7
1 8
2 8
1 7
1 6
1 3
5 8
4 4
2 3
1 1
1
1 1
3 3
3 2 1
1 2
1 3
2 3
8 1
1 2 3 4 5 6 7 8
1 8

Example output:
20 15 18 12 5 5 1 3
1
2 3 2
27

Editorial:
Let's iterate the left boundary of our queries $$$L$$$ from $$$n$$$ to $$$1$$$ and maintain the Fenwick tree $$$F$$$, where $$$F_i$$$ = the number of sought sets of indices in which $$$t_k = i$$$, and $$$t_1 \ge L$$$. Then the answer to the query with the left boundary at $$$L$$$ will be the sum over the interval $$$[l_i; r_i]$$$ in our Fenwick tree. Now we just need to learn how to update our tree when transitioning from $$$L$$$ to $$$L - 1$$$. Some new sets of indices may have been added, starting at $$$L - 1$$$. Let's denote $$$pos_i$$$ as the position of the number $$$i$$$ in the permutation. We'll create an auxiliary array $$$dp$$$. We'll learn to calculate the dynamics $$$dp_i = $$$ the number of sought sets of indices where $$$t_1 = L - 1$$$, $$$t_k = i$$$. The base case will be $$$dp_{L - 1} = 1$$$. Suppose we know the value of $$$dp_{pos_x}$$$. Then we can update $$$dp_{pos_y} = dp_{pos_y} + dp_{pos_x}$$$, if $$$y$$$ is divisible by $$$x$$$ and $$$y \ne x$$$, $$$pos_{a_i} \le pos_x \le pos_y$$$. We can calculate this dynamics straightforwardly, iterating over $$$x$$$ and $$$y$$$ $$$(y$$$ is divisible by $$$x$$$ and $$$x$$$ is divisible by $$$a_i)$$$. Notice that this will work in total for $$$O(n \cdot \log{n} \cdot \log{n})$$$ for the permutation. Now we can iterate over all numbers again that are multiples of $$$a_i$$$, update the Fenwick tree, and clear the $$$dp$$$ array to reuse it in the future.