2023 软件学院 ACM 集训队筛选赛
Problem F. 绝味鸭脖
给定 n 只老鼠排成一行，第 i 只老鼠的美味值是 a_i。这些老鼠可以转化为一棵鸭脖子树，满足：
- 有 n 个叶子节点，在中序遍历序列中，第 i 个出现的叶子节点的美味值为 a_i。
- 是二叉树，每个非叶子节点的美味值是它的左子树叶子节点最大美味值乘以右子树叶子节点的最大美味值。
- 树的美味值是所有节点的美味值之和。
给定老鼠，请你构造出美味值最小的鸭脖子树，并输出最小的美味值。
输入
输入一行一个整数 n(2\le n\le 2\times 10^5)。
接下来输入一行 n 个整数，第 i 个整数代表 a_i(1\le a_i\le 10^6)。
输出
输出一行一个整数，代表你的答案。
样例
| 标准输入 复制文本 |
2 1437 580 |
| 标准输出 复制文本 |
835477 |
| 标准输入 复制文本 |
3 6 2 4 |
| 标准输出 复制文本 |
44 |
| 标准输入 复制文本 |
6 1 1 4 5 1 4 |
| 标准输出 复制文本 |
65 |
提示
对样例一，仅能构造唯一的鸭脖子树如图所示(节点值表示美味值)，树的美味值为 1437+580+1437\times 580=835477
对样例二，能构造两种鸭脖子树，其中第一种鸭脖子树美味值最小，为 6+2+4+4\times 2+6\times 4=44
登录以提交代码。