Make Necklace Optimal#12834

Make Necklace Optimal

1 second
512 megabytes
Hard

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

Find out the maximum total value of the gems in the optimal necklace.

Input

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).

Output

Print an integer which denotes the maximum total value of the gems in the optimal necklace.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading