G. Бассейн и записи
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб плавают в бассейне под руководством своего инструктора Монокарпа.

Бассейн можно представить как отрезок на оси OX от $$$0$$$ по $$$50$$$. И Алиса, и Боб начали в момент $$$0$$$ в точке $$$0$$$ с положительными вещественными скоростями $$$v_A$$$ и $$$v_B$$$ соответственно.

И Алиса, и Боб плывут от $$$0$$$ до $$$50$$$, затем мгновенно разворачиваются и плывут от $$$50$$$ до $$$0$$$. В точке $$$0$$$ они снова поворачивают и плывут к $$$50$$$ и так далее.

Монокарп записал различную информацию о том, как плавали Алиса и Боб, включая моменты времени, когда они встречались в одной точке (Алиса и Боб плавают по параллельным дорожкам, так что они не мешают друг другу). Давайте назовем эти моменты времени последовательностью $$$t_1, t_2, \dots, t_n$$$.

Из-за некоторого инцидента Монокарп потерял почти все записанные данные, и все, что у него осталось,— это массив $$$t$$$. Монокарп помнит, что Алиса и Боб плавали с различными положительными вещественными скоростями $$$v_A$$$ и $$$v_B$$$ ($$$v_A > 0$$$; $$$v_B > 0$$$; $$$v_A \neq v_B$$$) и что последовательность $$$t$$$ содержит первые $$$n$$$ моментов встреч.

Но, глядя на последовательность $$$t$$$, он заметил, что все $$$t_i$$$ являются целыми числами. И теперь он сомневается, возможна ли такая последовательность $$$t$$$ или в ней есть какие-то ошибки. Помогите Монокарпу проверить массив $$$t$$$!

Входные данные

В первой строке задано одно целое число $$$c$$$ ($$$1 \le c \le 10^4$$$) — количество наборов входных данных. Затем следуют сами $$$c$$$ наборов.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер массива $$$t$$$.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$t_1, t_2, \dots, t_n$$$ ($$$1 \le t_1 < t_2 < \dots < t_n \le 10^9$$$) — моменты встреч в порядке возрастания.

Гарантируется, что сумма всех $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите VALID, если массив $$$t$$$ можно было получить, или, другими словами, существуют такие вещественные значения $$$v_A$$$ и $$$v_B$$$ ($$$v_A, v_B > 0$$$; $$$v_A \neq v_B$$$), что массив $$$t$$$ содержит первые $$$n$$$ моментов встреч Алисы и Боба в бассейне.

В противном случае выведите 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 = \frac{29}{21}$$$. Тогда в момент $$$42$$$ Алиса и Боб будут в точке $$$42$$$.

Во втором наборе представим, что $$$v_A = \frac{175}{6}$$$ и $$$v_B = \frac{25}{6}$$$. Тогда в момент $$$3$$$ Алиса и Боб встретятся в точке $$$12.5$$$, в $$$4$$$ они встретятся в точке $$$\frac{50}{3}$$$, в $$$6$$$ они встретятся в точке $$$25$$$ и в момент $$$8$$$ — в точке $$$\frac{100}{3}$$$. Поскольку это — в точности первые $$$4$$$ момента встреч, то массив $$$t$$$ — valid.

В третьем набора одна из возможных ситуаций: $$$v_A = 25$$$ и $$$v_B = 75$$$.