Eri and Expanded Sets
Contest: Codeforces Round 969 (Div. 1)
Difficulty rating: 2300
Tags: data structures, divide and conquer, math, number theory, two pointers

Let there be a set that contains distinct positive integers. To expand the set to contain as many integers as possible, Eri can choose two integers $$$x\neq y$$$ from the set such that their average $$$\frac{x+y}2$$$ is still a positive integer and isn't contained in the set, and add it to the set. The integers $$$x$$$ and $$$y$$$ remain in the set.

Let's call the set of integers consecutive if, after the elements are sorted, the difference between any pair of adjacent elements is $$$1$$$. For example, sets $$$\{2\}$$$, $$$\{2, 5, 4, 3\}$$$, $$$\{5, 6, 8, 7\}$$$ are consecutive, while $$$\{2, 4, 5, 6\}$$$, $$$\{9, 7\}$$$ are not.

Eri likes consecutive sets. Suppose there is an array $$$b$$$, then Eri puts all elements in $$$b$$$ into the set. If after a finite number of operations described above, the set can become consecutive, the array $$$b$$$ will be called brilliant.

Note that if the same integer appears in the array multiple times, we only put it into the set once, as a set always contains distinct positive integers.

Eri has an array $$$a$$$ of $$$n$$$ positive integers. Please help him to count the number of pairs of integers $$$(l,r)$$$ such that $$$1 \leq l \leq r \leq n$$$ and the subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ is brilliant.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 4 \cdot 10^5$$$) — length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$4 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the number of brilliant subarrays.

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

Note:
In the first test case, the array $$$a = [2, 2]$$$ has $$$3$$$ subarrays: $$$[2]$$$, $$$[2]$$$, and $$$[2, 2]$$$. For all of them, the set only contains a single integer $$$2$$$, therefore it's always consecutive. All these subarrays are brilliant, so the answer is $$$3$$$.

In the second test case, let's consider the subarray $$$[3, 6, 10]$$$. We can do operations as follows:

$$$$$$\{3,6,10\} \xrightarrow{x=6,y=10} \{3,6,8,10\} \xrightarrow{x=6,y=8} \{3,6,7,8,10\} \xrightarrow{x=3,y=7} \{3,5,6,7,8,10\}$$$$$$   $$$$$$\xrightarrow{x=3,y=5} \{3,4,5,6,7,8,10\} \xrightarrow{x=8,y=10} \{3,4,5,6,7,8,9,10\}$$$$$$

$$$\{3,4,5,6,7,8,9,10\}$$$ is a consecutive set, so the subarray $$$[3, 6, 10]$$$ is brilliant.

Example input:
6
2
2 2
6
1 3 6 10 15 21
5
6 30 18 36 9
1
1000000000
6
1 1 4 5 1 4
12
70 130 90 90 90 108 612 500 451 171 193 193

Example output:
3
18
5
1
18
53

Editorial:
Let's consider the elements in the final set $$$a$$$, and take $$$b_i=a_i-a_{i-1}$$$ as its difference array.
Observation 1: $$$b_i$$$ is odd. Otherwise we can turn $$$b_i$$$ into two $$$\frac{b_i}{2}$$$.
Observation 2: Adjacent $$$b_i$$$ are not different. Suppose $$$b_i$$$ and $$$b_{i+1}$$$ are different and odd, then $$$a_{i+1}-a_{i-1}$$$ is even, and $$$\frac{a_{i+1}+a_{i-1}}{2}\neq a_i$$$, so $$$a$$$ can be larger.
Thus, the array $$$a$$$ is an arithmetic progression, with an odd tolerance $$$b_i$$$.
If you notice this, and can also notice the monotonicity, you can maintain $$$(c,d,len)$$$ for a range of numbers to show that the final set is an arithmetic progression starting from $$$c$$$, consisting of $$$len$$$ elements and has tolerance $$$d$$$. It's amazing that two pieces of information like this can be merged, so we can use sparse table to maintain.
However, there's a better way to solve it. Similar to Euclidean Algorithm, the tolerance is equal to the maximum odd divisor of the gcd of the difference array of $$$a$$$, that is, $$$\gcd\{a_i-a_{i-1}\}$$$. Then the restriction means that $$$\gcd\{a_i-a_{i-1}\}$$$ is a power of $$$2$$$.
For a fixed point $$$l$$$, find the smallest $$$r$$$ that interval $$$[l,r]$$$ is good. A divisor of a power of $$$2$$$ is still a power of $$$2$$$, so it has monotonicity, which makes it possible to use two pointers to maintain it in $$$O(n\log nV)$$$ or $$$O(n\log V)$$$. Using sparse table or binary lifting may reach the same complexity. Note that adjacent same numbers should be carefully dealt with.