H. Do You Want to Build a Snowman?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eddie wants to build a snowman. In front of him is a field of snow, represented by an array $$$d$$$ of size $$$n$$$ where $$$d[i]$$$ is the depth of the snow at position $$$i$$$. Eddie can make a snowball by rolling together the snow in an interval $$$[x, y]$$$, where the size of the resulting ball is $$$s = \sum_{i=x}^y d[i]$$$. Eddie wants to make a three-ball snowman from three intervals $$$[1, l]$$$, $$$[l+1, r]$$$, and $$$[r+1, n]$$$ such that if the sizes of the balls are sorted as $$$s_1 \le s_2 \le s_3$$$, then $$$s_2 \ge 2s_1$$$ and $$$s_3 \ge 2s_2$$$. Eddie also wants a big snowman, so the value of $$$s_1$$$ should be as large as possible.

Can you help Eddie build a snowman meeting his requirements so that the size of the smallest snowball in the snowman is maximized?

Input

The first line of input contains $$$n$$$ ($$$3 \le n \le 10^5$$$), the size of the snow field.

The second line contains $$$n$$$ integers, $$$d_1, d_2, ..., d_n$$$ ($$$1 \le d_i \le 10^9$$$), the depth of the snow at each position.

Output

The output should be one line containing the maximum possible size of the smallest snowball in a valid snowman, or $$$-1$$$ if no valid snowman can be constructed.

Example
Input
4
2 1 1 3
Output
1
Note

Eddie can only build a valid snowman from the three intervals $$$[1, 1]$$$, $$$[2, 2]$$$, and $$$[3, 4]$$$. This results in a snowman with snowballs of size $$$2$$$, $$$1$$$, and $$$1+3=4$$$, so the smallest snowball is of size $$$1$$$.