310928: CF1910G. Pool Records

G. Pool Recordstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExampleInput

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

Output

VALID
VALID
VALID
INVALID
VALID
INVALID
INVALID

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$.

题目大意：
Alice和Bob在教练Monocarp的指导下在泳池游泳。泳池可以表示为OX轴上的从0到50的线段。Alice和Bob都在0时刻从0点出发，以正实数速度v_A和v_B游泳。他们都从0游到50点，然后立即转身从50游回0点，在0点再次转身游向50点，如此往复。Monocarp记录了Alice和Bob的所有有价值的信息，包括他们相遇的同一时刻（Alice和Bob在平行泳道游泳，所以不会互相干扰）。我们将这些时刻称为序列t_1, t_2, …, t_n。由于一些事故，Monocarp丢失了他记录的几乎所有数据，他现在只拥有数组t。Monocarp记得Alice和Bob有不同正实数的游泳速度v_A和v_B（v_A > 0; v_B > 0; v_A ≠ v_B），并且序列t包含前n个相遇时刻。但是，他注意到序列t中的所有t_i都是整数值，现在他怀疑序列t是否有效，或者其中是否存在错误。帮助Monocarp检查数组t！

输入数据格式：
第一行包含一个整数c（1 ≤ c ≤ 10^4）——测试用例的数量。然后是c个案例。
每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2 * 10^5）——数组t的大小。
每个测试用例的第二行包含n个整数t_1, t_2, …, t_n（1 ≤ t_1 < t_2 < … < t_n ≤ 10^9）——按递增顺序排列的相遇时刻。
保证所有测试用例的n之和不超过2 * 10^5。

输出数据格式：
对于每个测试用例，如果数组t是一个有效的数组，或者（换句话说）存在这样的实数值v_A和v_B（v_A, v_B > 0; v_A ≠ v_B），使得数组t包含Alice和Bob在泳池中前n个相遇时刻，则打印“VALID”。
否则，打印“INVALID”。
输出答案时大小写不敏感。例如，字符串“vALid”、“valid”、“Valid”和“VALID”都将被视为肯定响应。

示例：
输入：
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

输出：
VALID
VALID
VALID
INVALID
VALID
INVALID
INVALID

注意：
在第一个测试用例中，可以假设v_A = 1和v_B = 29/21。那么，在时刻42，Alice和Bob将在点42相遇。
在第二个测试用例中，可以假设v_A = 175/6和v_B = 25/6。那么，在时刻3，Alice和Bob将在点12.5相遇，在4时刻他们将在点50/3相遇，在时刻6他们将在点25相遇，在时刻8他们将在点100/3相遇。这正是前4个相遇时刻。数组t可能是有效的。
在第三个测试用例中，可能的情况之一是v_A = 25和v_B = 75。题目大意： Alice和Bob在教练Monocarp的指导下在泳池游泳。泳池可以表示为OX轴上的从0到50的线段。Alice和Bob都在0时刻从0点出发，以正实数速度v_A和v_B游泳。他们都从0游到50点，然后立即转身从50游回0点，在0点再次转身游向50点，如此往复。Monocarp记录了Alice和Bob的所有有价值的信息，包括他们相遇的同一时刻（Alice和Bob在平行泳道游泳，所以不会互相干扰）。我们将这些时刻称为序列t_1, t_2, …, t_n。由于一些事故，Monocarp丢失了他记录的几乎所有数据，他现在只拥有数组t。Monocarp记得Alice和Bob有不同正实数的游泳速度v_A和v_B（v_A > 0; v_B > 0; v_A ≠ v_B），并且序列t包含前n个相遇时刻。但是，他注意到序列t中的所有t_i都是整数值，现在他怀疑序列t是否有效，或者其中是否存在错误。帮助Monocarp检查数组t！ 输入数据格式： 第一行包含一个整数c（1 ≤ c ≤ 10^4）——测试用例的数量。然后是c个案例。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 2 * 10^5）——数组t的大小。 每个测试用例的第二行包含n个整数t_1, t_2, …, t_n（1 ≤ t_1 < t_2 < … < t_n ≤ 10^9）——按递增顺序排列的相遇时刻。 保证所有测试用例的n之和不超过2 * 10^5。 输出数据格式： 对于每个测试用例，如果数组t是一个有效的数组，或者（换句话说）存在这样的实数值v_A和v_B（v_A, v_B > 0; v_A ≠ v_B），使得数组t包含Alice和Bob在泳池中前n个相遇时刻，则打印“VALID”。 否则，打印“INVALID”。 输出答案时大小写不敏感。例如，字符串“vALid”、“valid”、“Valid”和“VALID”都将被视为肯定响应。 示例： 输入： 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 输出： VALID VALID VALID INVALID VALID INVALID INVALID 注意： 在第一个测试用例中，可以假设v_A = 1和v_B = 29/21。那么，在时刻42，Alice和Bob将在点42相遇。 在第二个测试用例中，可以假设v_A = 175/6和v_B = 25/6。那么，在时刻3，Alice和Bob将在点12.5相遇，在4时刻他们将在点50/3相遇，在时刻6他们将在点25相遇，在时刻8他们将在点100/3相遇。这正是前4个相遇时刻。数组t可能是有效的。 在第三个测试用例中，可能的情况之一是v_A = 25和v_B = 75。