D. 相邻重排 LCM 可分等差数列

    Type: Default 5000ms 512MiB

相邻重排 LCM 可分等差数列

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你正在参加国际构造排列大赛(International Construct Permutation Contest, ICPC),设 [ai]\left[ a_i \right] 是一个一共有 nn 项的整数数列。给定数列数字,请你将 [ai]\left[ a_i \right] 重新排列为 [pi]\left[ p_i \right] 并尝试求出

$$S=\sum_{i=1}^{n-1}\operatorname{lcm} (p_i,p_{i+1})$$

的最小值。

输入描述

第一行输入一个整数 nn 表示数列长度,满足 2⩽n⩽202\leqslant n \leqslant 20。

第二行输入 nn 个正整数 aia_i,满足 1⩽ai⩽1081\leqslant a_i\leqslant 10^8。

输出描述

输出一个数,表示 SS 的最小值。

样例

6
1 1 4 5 1 4
15
4
114 514 1919 810
235074
9
3 1 4 1 5 9 2 6 5
40

注释

对于第三组样例,满足条件的一种情况为:[9,3,6,2,4,1,1,5,5]\left[ 9,3,6,2,4,1,1,5,5 \right]。