+ Time Limit: 1 second + Memory Limit: 256 megabytes ----------- There are some fish standing in a queue. The weight of every fish except the first one is known, and the weight of the $i$-th fish is $a_i$. Fish $i$ can eat fish $j$ if and only if $a_j \leq a_i$. If fish $i$ eats fish $j$, the weight of fish $i$ will eventually become equal to the sum of the weights of the two fish, and fish $j$ will no longer be in the queue. As long as more than one fish remains in the queue, the following two steps are performed in order: + First, the first fish tries to eat the only fish adjacent to it. If the first fish cannot eat the fish in front of it, the game ends and the first fish loses. + Amirhosein, who hates the first fish, can choose some pairs of the remaining fish (including the first fish). He may choose no pairs. Each fish can belong to at most one pair, and two fish that are not adjacent to each other cannot be paired. Then, in each pair, Amirhosein forces the heavier fish to eat the lighter fish. If the two fish have equal weights, he may choose either one to eat the other. Amirhosein, determined to destroy the first fish, wants to find the minimum natural number $x$ such that if the weight of the first fish is $x$ $(a_1=x)$, then no matter how Amirhosein chooses the pairs during the game, the only fish remaining at the end of the game will be the first fish. # Input The first line contains an integer $n$, the number of fish. The second line contains $n-1$ integers representing the weights of the second through the $n$-th fish, respectively. $$ 1 \leq n \leq 3*10^5 $$ $$ 1 \leq a_i \leq 10^9 $$ # Output Print the minimum possible initial weight of the first fish such that the first fish cannot be eaten by any other fish, regardless of how the pairs are chosen. # Sample input 1 ``` 3 3 7 ``` # Sample output 1 ``` 5 ``` # Sample input 2 ``` 6 7 1 10 6 8 ``` # Sample output 2 ``` 16 ```