Congress and BJP$,$ two political rivals, are facing a mathematical challenge

related to their electoral numbers. They define a GCD sequence as follows: given an

array A of n positive integers, they calculate the GCD of each neighboring pair of

numbers to create a new array B$.$

The GCD sequence B is defined as follows: Bi $=$ GCD$($Ai$,$ Ai$+1$

$),$ for all $1<=$ i $<=$ n $-1.$

Congress and BJP are intrigued by the idea of transforming an array A by removing

exactly one number so that the resulting GCD sequence B is non$-$decreasing. They are

wondering if this is possible for various arrays they encounter.

Can you help them determine whether removing exactly one number from array A is

possible so that the resulting GCD sequence B is non$-$decreasing?

The required time complexity is less than O$($n$2$

$)$ and mention your proposed solution

time complexity in the code.

Here are the details:

Input format:

The first line contains a single integer n $$ the number of elements in the array A$.$

The second line contains n space$-$separated integers Ai $$ the electoral numbers of

array A$.$

Output format:

Output YES if it's possible to remove exactly one number from the array A so that the

resulting GCD$-$sequence B is non$-$decreasing. Otherwise, output NO$.$

Constraints:

$3<=$ n $<=2*105$

$1<=$ Ai $<=109$

Example $1$:

$9$

$57310631263$

Output: YES

Example $2$:

$5$

$1005021020$

Output: YES

Example $3$:

$10$

$7462451428$

Output: NO