Codeforces Round #505 -D-Recovering BST（区间DP）

D. Recovering BST

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Dima the hamster enjoys nibbling different things: cages, sticks, bad problemsetters and even trees!

Recently he found a binary search tree and instinctively nibbled all of its edges, hence messing up the vertices. Dima knows that if Andrew, who has been thoroughly assembling the tree for a long time, comes home and sees his creation demolished, he'll get extremely upset.

To not let that happen, Dima has to recover the binary search tree. Luckily, he noticed that any two vertices connected by a direct edge had their greatest common divisor value exceed 11.

Help Dima construct such a binary search tree or determine that it's impossible. The definition and properties of a binary search tree can be found here.

Input

The first line contains the number of vertices nn (2≤n≤7002≤n≤700).

The second line features nn distinct integers aiai (2≤ai≤1092≤ai≤109) — the values of vertices in ascending order.

Output

If it is possible to reassemble the binary search tree, such that the greatest common divisor of any two vertices connected by the edge is greater than 11, print "Yes" (quotes for clarity).

Otherwise, print "No" (quotes for clarity).

Examples

input

Copy

6
3 6 9 18 36 108

output

Copy

Yes

input

Copy

2
7 17

output

Copy

No

input

Copy

9
4 8 10 12 15 18 33 44 81

output

Copy

Yes

Note

The picture below illustrates one of the possible trees for the first example.

The picture below illustrates one of the possible trees for the third example.

题意：给你n个节点，每个节点有一个权值，两个点可以连边当且仅当这两个点的gcd>1,问你这n个点能否构成一个二叉搜索树（每个节点最多有两个儿子，且左儿子小于右儿子），输入为递增顺序。

题解：我们考虑区间dp，设两个数组L[l][r]和R[l][r]分别表示[l,r]这一区间内能否构成左子树和能否构成右子树，然后简单转移即可。（详见代码）

#include<stdio.h>
#define maxn 710
int n,a[maxn],L[maxn][maxn];
int R[maxn][maxn],g[maxn][maxn];
int gcd(int a,int b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
int main(void)
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),L[i][i]=R[i][i]=1;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			g[i][j]=gcd(a[i],a[j]);
	for (int l=n;l>=1;l--)
		for (int r=l;r<=n;r++)
			for (int k=l;k<=r;k++)
				if (L[l][k] && R[k][r])
				{
					if (l==1 && r==n)
					{
						printf("Yes\n");
						return 0;
					}
					if (g[l-1][k]>1) R[l-1][r]=1;
					if (g[k][r+1]>1) L[l][r+1]=1;
				}
	printf("No\n");
	return 0;
}