琥珀在宝岛收到了一只科学的“老鼠”，但是千空说这不是老鼠，这是鸭脖号四驱车。

给定 $n$ 只老鼠排成一行，第 $i$ 只老鼠的美味值是 $a_i$。这些老鼠可以转化为一棵鸭脖子树，满足：

1. 有 $n$ 个叶子节点，在中序遍历序列中，第 $i$ 个出现的叶子节点的美味值为 $a_i$。
2. 是二叉树，每个非叶子节点的美味值是它的左子树叶子节点最大美味值乘以右子树叶子节点的最大美味值。
3. 树的美味值是所有节点的美味值之和。
4. 每个非叶子节点必须拥有两个子节点。

给定老鼠，请你构造出美味值最大的鸭脖子树，并输出最大的美味值。

输入一行一个整数 $n(2\le n\le 2\times 10^5)$。

接下来输入一行 $n$ 个整数，第 $i$ 个整数代表 $a_i(1\le a_i\le 10^6)$。

输出一行一个整数，代表你的答案。

对样例一，仅能构造唯一的鸭脖子树如图所示(节点值表示美味值)，树的美味值为 $1437+580+1437\times 580=835477$

对样例二，能构造两种鸭脖子树，其中第二种鸭脖子树美味值最大，为 $6+2+4+6\times 2+6\times 4=48$