Pool Records
Contest: Kotlin Heroes: Episode 9 (Unrated, T-Shirts + Prizes!)
Difficulty rating: 2700
Tags: *special, greedy

Alice and Bob are swimming in the pool under the guidance of their instructor Monocarp.

The pool can be represented as a segment on the OX-axis from $$$0$$$ to $$$50$$$. Both Alice and Bob started at moment $$$0$$$ at point $$$0$$$ with positive real speeds $$$v_A$$$ and $$$v_B$$$ correspondingly.

Both Alice and Bob swim from $$$0$$$ to point $$$50$$$, then instantly turn back and swim from $$$50$$$ to $$$0$$$. At $$$0$$$ they turn back again and swim to $$$50$$$ and so on.

Monocarp logged all valuable info about Alice and Bob, including moments of time when they met at the same point (Alice and Bob swim on parallel lanes, so they don't bother each other). Let's name that moments of time as sequence $$$t_1, t_2, \dots, t_n$$$.

Due to some incident, Monocarp lost almost all data he recorded, and all he has now is array $$$t$$$. Monocarp remembers that Alice and Bob had distinct positive real swimming speeds $$$v_A$$$ and $$$v_B$$$ ($$$v_A > 0$$$; $$$v_B > 0$$$; $$$v_A \neq v_B$$$) and that sequence $$$t$$$ contains the first $$$n$$$ meeting moments.

But looking at sequence $$$t$$$ he noticed that all $$$t_i$$$ are integer values, and now he doubts is sequence $$$t$$$ valid or there are some errors in it. Help Monocarp to check array $$$t$$$!

Input format:
The first line contains a single integer $$$c$$$ ($$$1 \le c \le 10^4$$$) — the number of test cases. Then $$$c$$$ cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of array $$$t$$$.

The second line of each test case contains $$$n$$$ integers $$$t_1, t_2, \dots, t_n$$$ ($$$1 \le t_1 < t_2 < \dots < t_n \le 10^9$$$) — the meeting moments in the increasing order.

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

Output format:
For each test case, print VALID if the array $$$t$$$ is a valid array, or (in other words) exist such real values $$$v_A$$$ and $$$v_B$$$ ($$$v_A, v_B > 0$$$; $$$v_A \neq v_B$$$) that array $$$t$$$ contains the first $$$n$$$ meeting moments of Alice and Bob in the pool.

Otherwise, print INVALID.

You can output the answer in any case (upper or lower). For example, the strings "vALid", "valid", "Valid", and "VALID" will be recognized as positive responses.

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

Note:
In the first test case, imagine a situation: $$$v_A = 1$$$ and $$$v_B = \frac{29}{21}$$$. Then, at moment $$$42$$$ Alice and Bob will be at point $$$42$$$.

In the second test case, imagine a situation: $$$v_A = \frac{175}{6}$$$ and $$$v_B = \frac{25}{6}$$$. Then, at moment $$$3$$$ Alice and Bob will meet at point $$$12.5$$$, at $$$4$$$ they'll meet at point $$$\frac{50}{3}$$$, at moment $$$6$$$ they'll meet at $$$25$$$ and at moment $$$8$$$ — at point $$$\frac{100}{3}$$$. Since it's exactly the first $$$4$$$ meeting moments. Array $$$t$$$ may be valid.

In the third test case, one of the possible situations is $$$v_A = 25$$$ and $$$v_B = 75$$$.

Example input:
7
1
42
4
3 4 6 8
5
1 2 3 4 5
3
999999998 999999999 1000000000
5
4 6 8 12 16
4
6 11 12 14
2
10 30

Example output:
VALID
VALID
VALID
INVALID
VALID
INVALID
INVALID

Editorial:
There are basically two types of meetings between Alice and Bob: they meet while moving in opposite directions or while moving in the same direction (we will count meetings at the border of the pool as both types).
Let's look at these types independently. Suppose they are moving in the opposite directions and met at point $$$p_1$$$. Suppose, the next time they met in point $$$p_2$$$. The total distance they swim is $$$(p_1 + p_2) + (50 - p_1 + 50 - p_2) = 2 \cdot 50 = 100$$$. The total speed they travel until the next encounter is $$$v_A + v_B$$$.
So the period of time between two consecutive meeting moments are always $$$\frac{100}{v_A + v_B}$$$. Let's name it as short period $$$p_s$$$.
Analogically, let's analyze the case when they met while swimming in the same direction. Without loss of generality, let's say that $$$v_A > v_B$$$. Then the relative speed of Alice with respect to Bob is $$$|v_A - v_B|$$$ and they will meet again after Alice will swim one more cycle, or $$$100$$$. Then, the period of time between two meeting moments is $$$\frac{100}{|v_A - v_B|}$$$. Let's name it as long period $$$p_l$$$.
In total, we understand that all values $$$t_i$$$ must be divisible either by $$$p_s$$$ or by $$$p_l$$$, since Alice and Bob started at $$$0$$$, each meeting moment is one of two types and difference between moments of the same type must be equal to the corresponding period.
So, if we know both values $$$p_s$$$ and $$$p_l$$$ we can check is $$$t$$$ valid or not. Since $$$v_A, v_B > 0$$$ then $$$p_s < p_l$$$. And since $$$t_1$$$ is the first moment, then short period $$$p_s$$$ has to be equal to $$$t_1$$$.
So we know that $$$p_s = t_1$$$, but how to find $$$p_l$$$? Let's find the minimum $$$t_i$$$ such that $$$t_i$$$ is not divisible by $$$p_s$$$. Since it's not divisible by $$$p_s$$$ it has to be divisible by $$$p_l$$$. And it's not hard to prove that $$$p_l$$$ is exactly $$$t_i$$$. (We can prove it by contradiction: suppose $$$p_l = t_j$$$ ($$$j < i$$$); since all $$$t_j < t_i$$$ are divisible by $$$p_s$$$ then $$$p_l = t_j$$$ is also divisible by $$$p_s$$$, but $$$t_i$$$ is not divisible by $$$p_s$$$, so $$$t_i$$$ is not divisible by $$$p_l$$$ — contradiction).
So, now we know both $$$p_s$$$ and $$$p_l$$$, how to check: is $$$t$$$ valid? Let's just create an array $$$t'$$$ — the first $$$n$$$ meeting moments for a pair of periods $$$p_s$$$ and $$$p_l$$$ and compare it with a given array $$$t$$$.
To create $$$t'$$$ let's do the following:
1. create list $$$S = [p_s, 2 p_s, \dots, n \cdot p_s]$$$;
2. create list $$$L = [p_l, 2 p_l, \dots, n \cdot p_l]$$$;
3. merge $$$S$$$ and $$$L$$$ in one list $$$t'$$$ taking only unique values from both lists (for example, using union);
4. sort $$$t'$$$ if necessary and take only first $$$n$$$ elements from it.
If generated $$$t'$$$ and given $$$t$$$ are equal, then $$$t$$$ is a valid array, otherwise it's invalid.