Sắp mảng để nhiều số nguyên tố

Cho mảng \(A\) gồm \(N\) phần tử, mỗi phần tử chỉ là \(1\) hoặc \(2\). Bạn được phép hoán vị các phần tử của \(A\) theo thứ tự tuỳ ý.

Gọi \(P\) là mảng tổng tiền tố của \(A\) sau khi sắp xếp: \(P_i = A_1 + A_2 + \dots + A_i\). Hãy chọn cách sắp xếp sao cho mảng \(P\) chứa nhiều số nguyên tố nhất (đếm số vị trí \(i\) có \(P_i\) là số nguyên tố).

Input

• Dòng 1: số nguyên \(N\).
• Dòng 2: \(N\) số \(A_1, \dots, A_N\), mỗi số là \(1\) hoặc \(2\).

Output

• In ra số lượng số nguyên tố lớn nhất có thể có trong mảng \(P\).

Constraints

• \(1 \le N < 10^5\).

Sample Input

6
2 1 1 2 2 1

Sample Output

4

Explanation

Sắp xếp thành \([2,1,2,2,1,1]\) thì \(P=[2,3,5,7,8,9]\) có \(4\) số nguyên tố (\(2,3,5,7\)). Không có cách nào tốt hơn.