GCD-sequence
Contest: Codeforces Round 950 (Div. 3)
Difficulty rating: 1400
Tags: greedy, implementation, math, number theory

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

Input format:
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 format:
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).

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

Note:
The first test case is explained in the problem statement.

Example input:
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

Example output:
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES

Editorial:
Let's loop through the initial array $$$a$$$, counting the GCD of neighbouring elements. If at some point, the GCD of the previous pair becomes greater than the GCD of the next pair, we remember the index $$$i$$$ of the first element of the pair that gave the greater GCD and stop the loop.
Then consider the following cases:
• the sequence of GCDs for array $$$a$$$ was already non-decreasing. Then it is enough to remove the last element from it, the previous elements of the GCD-sequence will not be affected. The answer in this case is always YES.
• some element $$$a_i$$$ has been found such that $$$GCD(a_{i-1}, a_i) \gt GCD(a_i, a_{i+1})$$$. Then, since there is already at least one place in the original GCD-sequence where it ceases to be non-decreasing, we can try to fix it by removing the $$$i-1$$$-th, $$$i$$$-th or $$$i+1$$$-th element from the array $$$a$$$. Let's create $$$3$$$ new arrays of length $$$n-1$$$, and in each of them remove one of the above elements. If at least one of these arrays has a non-decreasing GCD-sequence — the answer is YES, otherwise — NO.