Bạn được cho một mảng A gồm N phần tử, trong đó các phần tử chỉ nhận giá trị 1 hoặc 2. Nhiệm vụ của bạn là viết chương trình sắp xếp lại mảng A thoả mãn:

+ Gọi P là mảng tổng tiền tố của A

+ P chứa nhiều số nguyên tố nhất

 Ví dụ: Bạn có A = [1, 2, 1, 2, 1], chúng ta sắp xếp mảng A này là A = [2, 1, 1, 1, 2], Khi đó mảng tiền tố P = [2, 3, 4, 5, 7]. Mảng P chứa 4 số nguyên tố. Đây là cách sắp xếp tốt nhất.

 Lưu ý: Mảng tồng tiền tố (Prefix sum) có rất nhiều ứng dụng, được tính như sau:

        + P[1] = A[1]

        + P[2] = A[1] + A[2]

        + P[3] = A[1] + A[2] + A[3]

        + ...

        + P[n] = P[n-1] + A[n]

Dữ liệu nhập:

• Dòng 1 là số nguyên dương N (0 < N < 10^5)

• Dòng 2 là dãy A

Kết quả:

• in ra màn hình số lượng số nguyên tố lớn nhất tạo ra được có mặt trong mảng tiền tố P trong cách sắp xếp tốt nhất.