/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
長さ N の数列 a = (a_1, a_2, ..., a_N) があります。 各 a_i は正の整数です。
すぬけ君の目標は、a の要素を自由に並べ替え、次の条件が成り立つようにすることです。
- 各 1 ≤ i ≤ N - 1 について、a_i と a_{i + 1} の積は 4 の倍数である。
すぬけ君が目標を達成できるか判定してください。
制約
- 2 ≤ N ≤ 10^5
- a_i は整数である。
- 1 ≤ a_i ≤ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
出力
すぬけ君が目標を達成できるならば Yes を、できないならば No を出力せよ。
入力例 1
3 1 10 100
出力例 1
Yes
例えば、(1, 100, 10) と並べ替えればよいです。
入力例 2
4 1 2 3 4
出力例 2
No
どのように並べ替えても、条件が成り立つようにできません。
入力例 3
3 1 4 1
出力例 3
Yes
最初から条件が成り立っています。
入力例 4
2 1 1
出力例 4
No
入力例 5
6 2 7 1 8 2 8
出力例 5
Yes
Score : 400 points
Problem Statement
We have a sequence of length N, a = (a_1, a_2, ..., a_N). Each a_i is a positive integer.
Snuke's objective is to permute the element in a so that the following condition is satisfied:
- For each 1 ≤ i ≤ N - 1, the product of a_i and a_{i + 1} is a multiple of 4.
Determine whether Snuke can achieve his objective.
Constraints
- 2 ≤ N ≤ 10^5
- a_i is an integer.
- 1 ≤ a_i ≤ 10^9
Input
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Output
If Snuke can achieve his objective, print Yes; otherwise, print No.
Sample Input 1
3 1 10 100
Sample Output 1
Yes
One solution is (1, 100, 10).
Sample Input 2
4 1 2 3 4
Sample Output 2
No
It is impossible to permute a so that the condition is satisfied.
Sample Input 3
3 1 4 1
Sample Output 3
Yes
The condition is already satisfied initially.
Sample Input 4
2 1 1
Sample Output 4
No
Sample Input 5
6 2 7 1 8 2 8
Sample Output 5
Yes