Subtask 1

First, let's try to determine whether a given array is good. Consider the ~k~-th element, ~x_k~. This element's index can only ever decrease, so it can never be divided by a number greater than ~k~. Thus, a necessary condition is that for each ~k~, ~x_k~ is a product of positive integers not exceeding ~k~; this is equivalent to saying that the largest prime factor of ~x_k~ is at most ~k~.

On the other hand, this condition is also sufficient. We can show this inductively:

• If the array is empty, we are already done.
• Otherwise, for each ~k~, while ~x_k~ is divisible by ~k~, divide ~x_k~ by ~k~. After this, the largest prime factor of ~x_k~ is now at most ~x_k - 1~, since it was at most ~x_k~ before division, and ~k~ does not divide ~x_k~.
• Delete the first element, which is allowed since ~x_1~ is guaranteed to be ~1~ for arrays satisfying the condition.
• Now, every other element's index decreases by 1, but the condition still holds. So we can inductively show that the remaining array can be made empty.

We can precalculate the largest prime factor of each integer from ~1~ up to ~\max(a_i)~ by modifying the Sieve of Eratosthenes.

For convenience, define ~p_k~ as the largest prime factor of ~a_k~. We now know that the condition for the subarray spanning the indexes ~[l, r]~ to be valid is that ~a_x \le x - l + 1~ for all ~l \le x \le r~. For this subtask, it is sufficient to brute force all ~l~, and loop to find the largest ~r~ such that the subarray ~[l, r]~ is valid.

Time complexity: ~\mathcal{O}(\max(a_i) \log\log(\max(a_i)) + N^2)~

Subtask 2

We need to speed up the counting of valid subarrays.

For a fixed ~l~, define index ~x~ as blocking if and only if ~a_x > x - l + 1~. The condition that the subarray spanning the indexes ~[l, r]~ is valid is now equivalent to saying that there are no blocking indexes between ~l~ and ~r~.

Loop ~l~ from ~N~ down to ~1~. The key insight here is that once an indexes stops becoming blocking, it will never become blocking again for any smaller ~l~. Thus, it suffices to maintain a stack of all blocking indexes. That is, when we try a new ~l~, we first add ~l~ onto the stack, and then pop off from the stack whilst the top element is non-blocking. The largest value of ~r~ such that the subarray ~[l, r]~ is valid is now the value on the top of the stack, minus ~1~.

Alternatively, for each ~l~, we can binary search for the largest ~r~ such that subarray ~[l, r]~ is valid, though we need a quick way to check whether ~[l, r]~ is valid. This can be done efficiently using a sparse table, or by walking down a segment tree.

Time complexity: ~\mathcal{O}(\max(a_i) \log\log(\max(a_i)) + N)~ or ~\mathcal{O}(\max(a_i) \log\log(\max(a_i)) + N \log N)~