【CodeForces - 1150C】Prefix Sum Primes（思维）

题干：

We're giving away nice huge bags containing number tiles! A bag we want to present to you contains nn tiles. Each of them has a single number written on it — either 11or 22.

However, there is one condition you must fulfill in order to receive the prize. You will need to put all the tiles from the bag in a sequence, in any order you wish. We will then compute the sums of all prefixes in the sequence, and then count how many of these sums are prime numbers. If you want to keep the prize, you will need to maximize the number of primes you get.

Can you win the prize? Hurry up, the bags are waiting!

Input

The first line of the input contains a single integer nn (1≤n≤2000001≤n≤200000) — the number of number tiles in the bag. The following line contains nn space-separated integers a1,a2,…,ana1,a2,…,an (ai∈{1,2}ai∈{1,2}) — the values written on the tiles.

Output

Output a permutation b1,b2,…,bnb1,b2,…,bn of the input sequence (a1,a2,…,an)(a1,a2,…,an) maximizing the number of the prefix sums being prime numbers. If there are multiple optimal permutations, output any.

Examples

Input

5
1 2 1 2 1

Output

1 1 1 2 2

Input

9
1 1 2 1 1 1 2 1 1

Output

1 1 1 2 1 1 1 2 1

Note

The first solution produces the prefix sums 1,2,3,5,71,2,3,5,7 (four primes constructed), while the prefix sums in the second solution are 1,2,3,5,6,7,8,10,111,2,3,5,6,7,8,10,11 (five primes). Primes are marked bold and blue. In each of these cases, the number of produced primes is maximum possible.

题目大意：

给你N个数，每个数都是1或者2.现在让你求一个排列，使得这个排列的前缀和数组拥有最多的素数。

解题报告：

直接贪心就行了，不难发现到3以后，就先填2，，不够再填1，这样一定是最优的。（因为你凑出了一个奇数，并且素数一定是奇数，而整个序列的最后一个数又是一定的，也就是前缀和数组的最后一个数一定是sum(ai)，是个定值，所以这样构造一定是最优解。）

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int n,a[MAX],bk[3];
int ans[MAX];
int main()
{
	cin>>n;
	for(int i = 1; i<=n; i++) cin>>a[i],bk[a[i]]++;
	sort(a+1,a+n+1,greater<int>());
	int cur = 0,top = 0,tar;
	for(int i = 1; i<=n; i++) {
		cur += a[i];bk[a[i]]--;ans[++top]=a[i];
		if(cur == 2) {tar = i;break;	}
	}
	if(bk[1]>0) bk[1]--,cur+=1,ans[++top]=1,n--;
	for(int i = tar+1; i<=n; i++) {
		cur+=a[i];bk[a[i]]--;
		ans[++top]=a[i];
	}
	for(int i = 1; i<=top; i++) printf("%d%c",ans[i],i == top ? '\n' :' ');
	return 0 ;
}

注意姿势啊：第一个for的bk[a[i]]--别放在if中。第二个for别直接i<=n-1，，因为有可能进不去上面那个if。。会造成输出的个数不是n个数。