小红的素数合并
题号:NC273647
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小红拿到了一个数组,其中每个元素都是素数。小红准备进行若干次以下操作:
选择两个素数元素,将他们合并,生成的新元素为原来两个素数的乘积。
现在小红希望操作到不能再操作为止,然后使得最终的极差(最大值减最小值)尽可能小。你能帮帮她吗?

输入描述:

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

输出描述:

一个整数,代表合并后的数组的极差。
示例1

输入

复制
4
2 3 5 3

输出

复制
1

说明

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