Everything Everywhere

The main trick is realizing this problem is way less about subarrays and way more about a brutal structural constraint.

Observation 1: A good subarray cannot be long

Take any good subarray, and let

$$g = \gcd(a_l, a_{l+1}, \dots, a_r), \quad m = \min(a_l,\dots,a_r), \quad M = \max(a_l,\dots,a_r).$$

The definition says

$$M - m = g.$$

But because $g$ is the gcd, it divides every element of the subarray. In particular,

$$g \mid m \quad \text{and} \quad g \mid M.$$

Since $M=m+g$, both endpoints are multiples of $g$.

Now look at the interval $[m, M] = [m, m+g]$. How many multiples of $g$ can lie inside an interval of length exactly $g$?

Only two: the endpoints themselves.

So every element in the subarray, being divisible by $g$ and lying between $m$ and $M$, must be either

$$m \quad \text{or} \quad M.$$

That already means a good subarray contains at most two distinct values.

But the array is a permutation, so all values are distinct. Therefore a good subarray can have at most $2$ elements.

Observation 2: Length $1$ is impossible

A subarray of length $1$ has

$$\max - \min = 0,$$

while

$$\gcd([x]) = x \ge 1.$$

So length $1$ is never good.

Therefore:

Every good subarray has length exactly $2$.

That’s the whole damn problem, honestly.

Observation 3: Characterizing a good pair

Now we only need to check adjacent pairs $(p_i, p_{i+1})$. A pair is good iff

$$|p_i - p_{i+1}| = \gcd(p_i, p_{i+1}).$$

So the answer is simply

$$\#\{i \mid 1 \le i < n,\ \gcd(p_i,p_{i+1}) = |p_i-p_{i+1}|\}.$$

If you like the number-theory flavor, let $x<y$ and $d=y-x$. Then

$$\gcd(x,y)=\gcd(x,x+d)=\gcd(x,d).$$

Hence the pair is good iff

$$\gcd(x,d)=d \iff d \mid x.$$

So good pairs are exactly pairs of the form

$$(kd, (k+1)d)$$

for some integers $k,d \ge 1$. Examples: $(1,2)$, $(2,4)$, $(3,6)$, $(4,6)$, etc.

But for implementation, just checking gcd directly is cleaner and more idiot-proof.

Algorithm

For each test case:

1. Read $n$ and the permutation $p$.
2. Initialize ans = 0.
3. For every $i$ from $0$ to $n-2$:
   • compute $g = \gcd(p[i], p[i+1])$,
   • if $$g = |p[i]-p[i+1]|,$$ increment ans.
4. Output ans.

Correctness sketch

We proved:

• Any good subarray must have length at most $2$.
• Length $1$ is impossible.
• Therefore the only candidates are length-$2$ subarrays.
• A length-$2$ subarray $[x,y]$ is good exactly when $$\max(x,y)-\min(x,y)=\gcd(x,y),$$ i.e. $$|x-y| = \gcd(x,y).$$

So counting exactly those adjacent pairs gives the exact answer.

No hidden gremlins. No segment trees. No black magic. Just a clean observation and a loop.

Complexity

For each test case we do $n-1$ gcd computations, so the complexity is

$$O(n \log V),$$

where $V \le n$ is the value size. Since the total $n$ over all test cases is at most $2\cdot 10^5$, this is easily fast enough.

Memory usage is

$$O(n)$$

for storing the permutation, or even $O(1)$ extra beyond the array.