素数极差

在n个素数的数字序列中，你准备进行若干次以下操作： 选择两个素数元素，将他们合并，生成的新元素为原来两个素数的乘积。 现在你希望操作到不能再操作为止，然后使得最终的极差（最大值减最小值）尽可能小。请输出极差值？

输入

第一行输入一个正整数n，代表小红拿到的数组。 第二行输入n个正整数ai，代表数组中的元素。保证ai是素数。 1≤n≤10^5 2≤ai≤10^9

输出

一个整数，代表合并后的数组的极差。

样例

输入

4
2 3 5 3

输出

1

提示

合并两次，分别合并2,5以及3,3，形成的数组是[9,10]，极差是10-9=1。

———————————————————————————————————————————

代码：

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+10;
long long a[N];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	int l=0,r=n-n%2-1;
	long long minn=1e18,maxx=0;
	while(l<r)
	{
		minn=min(minn,a[l]*a[r]);
		maxx=max(maxx,a[l]*a[r]);
		l++;
		r--;
	}
	if(n&1)
	{
		minn=min(minn,a[n-1]);
		maxx=max(maxx,a[n-1]);
	}
	cout<<maxx-minn;
	return 0;
}