Problem Statement

Mr. AtCoder made a round chocolate cake for his $2N$ friends. It is radially cut from the center into $2N$ equal pieces, numbered $0$ through $2N-1$ in clockwise order.

To give the final touches, he is going to put strawberries on each piece. He has heard what his friends want about it. The friends are numbered $0$ through $2N-1$, and Friend $i$ $(0 \leq i \leq 2N-1)$ wants the following:

• Piece $i, i+1, \dots, i+N-1$ have a total of at least $A_i$ strawberries on them (for $x \geq 2N$, consider Piece $x$ as Piece $x-2N$).

To fulfill the requests of all his friends, at least how many strawberries should be put on the whole cake?

Constraints

• $1 \leq N \leq 150000$
• $0 \leq A_i \leq 5 \times 10^8 \ (0 \leq i \leq 2N-1)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 \cdots A_{2N-1}

Output

Print the minimum number of strawberries that should be put on the whole cake to fulfill the requests of the friends.