Baumkuchen

JOI and his two sisters share a baumkuchen, a circular cake with N pre-cut notches. Cuts are allowed only at those notches. Between notch i and i+1 the piece size is Ai (and AN is between notch N and notch 1).

JOI cuts the cake into three pieces, keeps the smallest piece, and gives the other two to his sisters. Find the maximum possible value of the smallest piece among all valid cuts.

• Line 1: integer N
• Next N lines: integer Ai

Print the maximum achievable size of the smallest of the three pieces.

• 3 ≤ N ≤ 100 000
• 1 ≤ Ai ≤ 1 000 000 000