题目描述

给定长度为 $n$ 的数列 $a$ 和一张有 $n$ 个结点的带权完全无向图，结点 $u$ 和结点 $v$ 之间有一条权值为 $a_u \times a_v$ 的边，求该图的最小生成树。

输入格式

第一行一个正整数 $n$。

接下来一行 $n$ 个整数 $a_1,a_2,\ldots a_n$。

输出格式

一行一个整数表示答案。

3
1 2 3

5

4
1 1 -1 -1

-3

数据范围

对于 $10\%$ 的数据，$n=2$。

对于 $20\%$ 的数据，$n\le 800$。

对于 $40\%$ 的数据，$n\le 6000$。

对于另外 $10\%$ 的数据，$a_i\ge 0$。

对于 $100\%$ 的数据，$2 \le n \le 5 \times 10 ^ 5$，$|a_i| \le 10 ^ 6$。