思路:贪心 + 数学

step1:答案结构

直观显然是将同种粒子连续排列，即 1,...,1,2,...,2 这种排列交互能总和最小。

因为对于固定的区间长度，设其中有 $x$ 个 α 粒子（用 1 表示）和 $y$ 个 β 粒子（用 2 表示），交互能为 $(x+1)(y+1)$。如果区间内只有一种粒子（比如全是 α），则 $y=0$，交互能为 $x+1$；如果两种粒子都有，则 $x\ge 1,y\ge 1$，交互能 $(x+1)(y+1) \ge (x+y)+2 > (x+y)+1$。所以尽量让区间内相同粒子尽可能多，从而使总交互能最小。

题目内容

在实验室中，科学家获得了一排粒子，每个粒子要么是 α 粒子（用数字 1 表示），要么是 β 粒子（用数字 2 表示）。这些粒子排成一个长度为 $n$ 的数组。

对于一个连续子数组，设其中包含 $x$ 个 α 粒子和 $y$ 个 β 粒子，则该子数组的“交互能”定义为 $(x+1) \times (y+1)$。整个阵列的总交互能等于所有连续子数组的交互能之和。

科学家可以随意重新排列这些粒子的顺序。请计算出通过最优重排后，总交互能的最小可能值。

约束：数组长度 $n$ 不超过 $10^5$，数组中的每个整数只能是 1 或 2。

输入描述

第一行包含一个整数 $n$，表示数组长度。 第二行包含 $n$ 个整数，每个整数均为 1 或 2，表示初始的粒子序列。注意：最终答案只与两种粒子的数量有关。

输出描述

输出一个整数，表示最优排列下所有连续子数组交互能之和的最小值。

样例1

输入

1
2

输出

2

说明

数组中只有一个元素 2。其连续子数组仅有 [2]，乘积为 2，2 的因子有 1 和 2，共 2 个，因此权值为 2，总权值之和为 2。若该元素为 3，结果同样为 2。

样例2

输入

2
2 3

输出

8

说明

数组为 [2, 3]。无论是否重排，所有连续子数组的权值之和恒为 8：

• 子数组 [2]：乘积 2，因子个数 2，权值 2
• 子数组 [3]：乘积 3，因子个数 2，权值 2
• 子数组 [2, 3]：乘积 2×3=6，6 的因子有 1、2、3、6，共 4 个，权值 4 三者相加得 2+2+4=8。重排为 [3, 2] 总和也是 8，故最小可能值为 8。

样例3

输入

3
2 2 3

输出

19

说明

数组包含两个 2 和一个 3。通过将 3 放在一端得到排列 [3, 2, 2]，可使总权值最小：

• 长度为 1 的子数组：[3]（权值 2）、[2]（权值 2）、[2]（权值 2）
• 长度为 2 的子数组：[3, 2] 乘积 6，因子个数 4，权值 4；[2, 2] 乘积 4，因子有 1、2、4，共 3 个，权值 3
• 长度为 3 的子数组：[3, 2, 2] 乘积 12，因子有 1、2、3、4、6、12，共 6 个，权值 6 总和为 2+2+2 + 4+3 + 6 = 19。若采用其他排列（如 [2, 3, 2]），总和为 20，因此最小可能值为 19。