frog has $n$ gems arranged in a cycle, whose beautifulness are $a_1, a_2, \dots, a_n$. She would like to remove some gems to make them into a beautiful necklace without changing their relative order.
Note that a beautiful necklace can be divided into $3$ consecutive parts $X, y, Z$, where
- $X$ consists of gems with non-decreasing beautifulness,
- $y$ is the only perfect gem. (A perfect gem is a gem whose beautifulness equals to $10000$)
- $Z$ consists of gems with non-increasing beautifulness.
Find out the maximum total beautifulness of the remaining gems.
Input
The input consists of multiple tests. For each test:
The first line contains $1$ integer $n$ ($1 \leq n \leq 10^5$). The second line contains $n$ integers $a_1, a_2, \dots, a_n$. ($0 \leq a_i \leq 10^4$, $1 \leq \textrm{number of perfect gems} \leq 10$).
Output
For each test, write $1$ integer which denotes the maximum total remaining beautifulness.
Sample Input
6 10000 3 2 4 2 3 2 10000 10000
Sample Output
10010 10000