Подільна перестановка#12960

Подільна перестановка

2 seconds
512 megabytes
Hard

Вам задано послідовність з невід’ємних цілих чисел.

Визначте, чи існує послідовність , яка є перестановкою такою, що b_i є кратним (b_{i+1} + b_{i+2}) для всіх 1 \le i \le n - 2.

Input

У першому рядку задано ціле число – кількість елементів у послідовності .

У другому рядку задано цілих чисел a_i – елементи послідовності .

3 \le n \le 10^6,

1 \le a_i \le 10^9.

Output

Якщо існує послідовність , яка задовольняє умову, виведіть Yes. Інакше виведіть No.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

У першому прикладі послідовність b = (4444, 40, 4, 4) задовольняє умову.

  • b_1 = 4444 є кратним b_2 + b_3 = 40 + 4 = 44.

  • b_2 = 40 є кратним b_3 + b_4 = 4 + 4 = 8.

У другому прикладі не існує послідовності, яка задовольняє умову.