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.