Bytica has gems arranged in a cycle, whose values are a_1, a_2, \dots, a_n. She would like to remove some gems to make them into a optimal necklace without changing their relative order.
Note that an optimal necklace can be divided into 3 consecutive parts , , , where
consists of gems with non-decreasing values,
is the only diamond. (A diamond is a gem whose value equals to )
consists of gems with non-increasing values.
Find out the maximum total value of the gems in the optimal necklace.
The first line of the input contains one integer (1 \leq n \leq 10^5).
The second line contains integers a_1, a_2, \dots, a_n — values of gems (0 \leq a_i \leq 10^4, 1 \leq \textrm{number of diamonds} \leq 10).
Print an integer which denotes the maximum total value of the gems in the optimal necklace.
Example 1
Example 2