frog 有 $n$ 颗宝石排成一个环，其“美观度”分别为 $a_1, a_2, \dots, a_n$。 她想要移除一些宝石，在保持剩余宝石相对顺序不变的前提下，将它们组成一条“美丽的项链”。
注意，一条“美丽的项链”可以被分为 $3$ 个连续的部分 $X, y, Z$，其中：
- $X$ 由美观度非递减的宝石组成。
- $y$ 是唯一的“完美宝石”。（“完美宝石”是指美观度等于 $10000$ 的宝石）。
- $Z$ 由美观度非递增的宝石组成。
求剩余宝石的美观度之和的最大值。
输入格式
输入包含多组测试数据。对于每组测试：
第一行包含 $1$ 个整数 $n$ ($1 \leq n \leq 10^5$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq 10^4$，$1 \leq \text{完美宝石的数量} \leq 10$)。
输出格式
对于每组测试，输出 $1$ 个整数，表示剩余宝石美观度之和的最大值。
样例
样例输入 1
6 10000 3 2 4 2 3 2 10000 10000
样例输出 1
10010 10000