题目描述

某数据分析系统收到一个长度为 $n$ 的非负整数序列 $a$。现在需要将序列中的所有元素划分到两个非空子序列 $b$ 和 $c$ 中。

子序列中的元素不要求在原序列中连续，但需要保持它们在原序列中的相对顺序。每个元素必须且只能被分配到其中一个子序列。

对于子序列 $b$，定义它的得分参数为其中所有元素的最小值，即 $\min(b)$。

对于子序列 $c$，定义 $\operatorname{mex}(c)$ 为其中没有出现过的最小非负整数。例如：

• $\operatorname{mex}([0,1,3])=2$；
• $\operatorname{mex}([1,2,3])=0$；
• $\operatorname{mex}([0,1,2])=3$。

本次划分的最终得分为 $\min(b)$ 与 $\operatorname{mex}(c)$ 的乘积。

你可以自由决定每个元素属于哪个子序列。请计算所有合法划分中能够得到的最大得分。

输入格式

第一行输入一个正整数 $n$，表示序列 $a$ 的长度。

第二行输入 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，表示序列中的元素。

输出格式

输出一行一个非负整数，表示能够得到的最大乘积。

3
0 1 2

4

样例 1 解释

可以把序列 $a$ 划分成两个子序列 $[2]$ 和 $[0,1]$，前者的最小值是 $2$，后者最小未出现的非负整数是 $2$，乘积为 $4$。

7
1 9 1 9 8 1 0

18

样例 2 解释

可以把序列 $a$ 划分成两个子序列 $[9,9]$ 和 $[1,1,8,1,0]$，前者的最小值是 $9$，后者最小未出现的非负整数是 $2$，乘积为 $18$。

6
1 1 4 5 1 4

0

样例 3 解释

可以把序列 $a$ 划分成两个子序列 $[1,1,4]$ 和 $[5,1,4]$，前者的最小值是 $1$，后者最小未出现的非负整数是 $0$，乘积为 $0$。

数据范围

对于所有数据，$2\le n\le 5\times10^5$，$0\le a_i\le 10^9$。

本题采用捆绑测试。

• 子任务 1（15 分）：$n\le 20$。
• 子任务 2（27 分）：$n\le 5\times10^3$。
• 子任务 3（16 分）：$a_i\le 1$。
• 子任务 4（3 分）：$a_i\ge 1$。
• 子任务 5（39 分）：无特殊限制。