题目内容

小红是一位喜欢玩数字游戏的小朋友。有一天，他在网上看到了一个有趣的挑战：

给定一个仅包含 $2$ 和 $3$ 的数组，如何重新排列它，使得所有连续子数组的权值之和尽可能小？数组的权值定义为数组所有元素乘积的因子数量。

例如，数组 $[2,3]$ 的权值为 $4$ ，因为 $2∗3=6$ 有 $4$ 个因子： $1、2、3、6$ 。

小红觉得这个挑战很有意思，就决定试试看。他拿出了一些卡片，每张卡片上写着 $2$ 或 $3$ ，并把它们排成了一个数组。然后，他开始思考如何重新排列这些卡片，使得所有连续子数组的权值之和最小。

他发现，这个问题并不简单，因为不同的排列方式会导致不同的结果。他想请你帮帮他，告诉他应该如何排列这些卡片，以及最小的权值之和是多少。

输入描述

输入第一行为一个整数 $n(1 \leq n \leq 1e5)$ ，表示数组的长度。

输入第二行为一个长度为 $n$ 的数组，第 $i$ 个整数为 $a_i$ 。

输出描述

输出为一个正整数，代表重排后，所有连续子数组权值之和的最小值。

样例

输入

2
2 3

输出

8

样例解释

无论是否重排，该数组的连续子数组权值之和都是 $8$ ：

$[2]$ 的权值为 $2$ 。 $[3]$ 的权值为 $2$ 。 $[2,3]$ 的权值为 $4$ 。

思考

$n \leq 1e9$ 如何解决?

思路:贪心 + 数学

step1:答案结构

直观显然是$2,...,2,3,...,3$ 这种排列权值和最小。

因为考虑一个固定的区间长度，$d(2^{k}) = k + 1 , d(2^{x} * 3^{k-x}) = (x+1) * (k-x+1) > d(2^{k})$。 所以肯定是让区间内相同数尽量多。