Divisible Array

Limits: 2 sec., 512 MiB

You are given a sequence $a$ of $n$ non-negative integers.

Determine if there exists a sequence $b$ that is a permutation of $a$ such that $b_i$ is a multiple of $(b_{i+1} + b_{i+2})$ for all $1 \le i \le n - 2$.

Input

The first line contains an integer $n$ – the number of elements in sequence $a$.

The second line contains $n$ integers $a_i$ – the elements of sequence $a$.

Output

If there exists a sequence $b$ satisfying the condition, print Yes. Otherwise, print No.

Constraints

$3 \le n \le 10^6$,

$1 \le a_i \le 10^9$.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 40 4444 4 4	Yes

Input (stdin) сopy	Output (stdout) сopy
7 4 7 77 4 477 4747 777444777	No

Notes

In the first example, the sequence $b = (4444, 40, 4, 4)$ satisfies the condition.

• $b_1 = 4444$ is a multiple of $b_2 + b_3 = 40 + 4 = 44$.

• $b_2 = 40$ is a multiple of $b_3 + b_4 = 4 + 4 = 8$.

In the second example, there does not exist a sequence satisfying the condition.