← 返回题目列表

AtCoder · pakencamp_2023_day1_g

G. MST(简单)

中文机器翻译题面 查看原题

配点 : 400 点

問題文

长度 小于或等于 N 整数序列 给出 A 。 对于

頂点 u 和 边缘 v 的边的权重为 完整的图表是 A_u\times A_v 求 G 的最小生成树的权重。 连接

制約

  • 2 \leq N \leq 2\times 10^5
  • |A_i| \le 10^6
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \ldots A_N

出力

打印答案。 来自


入力例 1

3
1 2 3

出力例 1

5

頂点 1 和 边缘 2 的边的权重为 1\times 2=2 、

頂点 1 和 边缘 3 的边的权重为 1\times 3=3 、

頂点 2 和 边缘 3 的边的权重为 2\times 3=6 。

因此 连接 1 和 按字典顺序比较 2 的边, 最少是创建一棵边连接 1 和 按字典顺序比较 3 的生成树,这棵树的权重为 5 。


入力例 2

4
1 1 -1 -1

出力例 2

-3