311393: CF1980D. GCD-sequence

D. GCD-sequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

GCD (Greatest Common Divisor) of two integers $x$ and $y$ is the maximum integer $z$ by which both $x$ and $y$ are divisible. For example, $GCD(36, 48) = 12$, $GCD(5, 10) = 5$, and $GCD(7,11) = 1$.

Kristina has an array $a$ consisting of exactly $n$ positive integers. She wants to count the GCD of each neighbouring pair of numbers to get a new array $b$, called GCD-sequence.

So, the elements of the GCD-sequence $b$ will be calculated using the formula $b_i = GCD(a_i, a_{i + 1})$ for $1 \le i \le n - 1$.

Determine whether it is possible to remove exactly one number from the array $a$ so that the GCD sequence $b$ is non-decreasing (i.e., $b_i \le b_{i+1}$ is always true).

For example, let Khristina had an array $a$ = [$20, 6, 12, 3, 48, 36$]. If she removes $a_4 = 3$ from it and counts the GCD-sequence of $b$, she gets:

• $b_1 = GCD(20, 6) = 2$
• $b_2 = GCD(6, 12) = 6$
• $b_3 = GCD(12, 48) = 12$
• $b_4 = GCD(48, 36) = 12$

The resulting GCD sequence $b$ = [$2,6,12,12$] is non-decreasing because $b_1 \le b_2 \le b_3 \le b_4$.Input

The first line of input data contains a single number $t$ ($1 \le t \le 10^4$) — he number of test cases in the test.

This is followed by the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$.

The second line of each test case contains exactly $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the elements of array $a$.

It is guaranteed that the sum of $n$ over all test case does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single line:

• "YES" if you can remove exactly one number from the array $a$ so that the GCD-sequence of $b$ is non-decreasing;
• "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will all be recognized as a positive answer).

ExampleInput

12
6
20 6 12 3 48 36
4
12 6 3 4
3
10 12 3
5
32 16 8 4 2
5
100 50 2 10 20
4
2 4 8 1
10
7 4 6 2 4 5 1 4 2 8
7
5 9 6 8 5 9 2
6
11 14 8 12 9 3
9
5 7 3 10 6 3 12 6 3
3
4 2 4
8
1 6 11 12 6 12 3 6

Output

YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES

Note

The first test case is explained in the problem statement.

题目大意：
这个题目是关于最大公约数（GCD）的序列问题。给定一个正整数数组a，长度为n，要求计算一个新数组b，称为GCD序列，其元素由公式b_i = GCD(a_i, a_{i + 1})计算得出，对于1 ≤ i ≤ n - 1。需要判断是否可以通过删除数组a中的恰好一个数字，使得GCD序列b是非递减的（即b_i ≤ b_{i+1}始终成立）。

输入输出数据格式：
输入：
- 第一行是一个整数t，表示测试用例的数量，1 ≤ t ≤ 10^4。
- 每个测试用例的描述如下：
- 第一行是一个整数n，表示数组a的元素数量，3 ≤ n ≤ 2 × 10^5。
- 第二行包含n个整数a_i，表示数组a的元素，1 ≤ a_i ≤ 10^9。

输出：
- 对于每个测试用例，输出一行：
- 如果可以通过删除数组a中的恰好一个数字使得GCD序列b非递减，则输出“YES”。
- 否则输出“NO”。

请注意，t个测试用例的n之和不超过2 × 10^5。

示例输入输出：
输入：
```
12
6
20 6 12 3 48 36
4
12 6 3 4
3
10 12 3
5
32 16 8 4 2
5
100 50 2 10 20
4
2 4 8 1
10
7 4 6 2 4 5 1 4 2 8
7
5 9 6 8 5 9 2
6
11 14 8 12 9 3
9
5 7 3 10 6 3 12 6 3
3
4 2 4
8
1 6 11 12 6 12 3 6
```
输出：
```
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
```题目大意： 这个题目是关于最大公约数（GCD）的序列问题。给定一个正整数数组a，长度为n，要求计算一个新数组b，称为GCD序列，其元素由公式b_i = GCD(a_i, a_{i + 1})计算得出，对于1 ≤ i ≤ n - 1。需要判断是否可以通过删除数组a中的恰好一个数字，使得GCD序列b是非递减的（即b_i ≤ b_{i+1}始终成立）。 输入输出数据格式： 输入： - 第一行是一个整数t，表示测试用例的数量，1 ≤ t ≤ 10^4。 - 每个测试用例的描述如下： - 第一行是一个整数n，表示数组a的元素数量，3 ≤ n ≤ 2 × 10^5。 - 第二行包含n个整数a_i，表示数组a的元素，1 ≤ a_i ≤ 10^9。 输出： - 对于每个测试用例，输出一行： - 如果可以通过删除数组a中的恰好一个数字使得GCD序列b非递减，则输出“YES”。 - 否则输出“NO”。 请注意，t个测试用例的n之和不超过2 × 10^5。 示例输入输出： 输入： ``` 12 6 20 6 12 3 48 36 4 12 6 3 4 3 10 12 3 5 32 16 8 4 2 5 100 50 2 10 20 4 2 4 8 1 10 7 4 6 2 4 5 1 4 2 8 7 5 9 6 8 5 9 2 6 11 14 8 12 9 3 9 5 7 3 10 6 3 12 6 3 3 4 2 4 8 1 6 11 12 6 12 3 6 ``` 输出： ``` YES NO YES NO YES YES NO YES YES YES YES YES ```