friends

Adisor realized that part of his troubles were due to the fact that he didn't choose his friends right. Therefore, he has made an important decision: he is going to give up on some of them.
Here's how he went about it: first he numbered all his n friends from 1 to n. Then he attached to each friend i, an integer C_i, called "quality", which in Adisor's mind represented the algebraic sum of the qualities and defects of that person. Afterwards, he drew a circle and on its side he entered, in order, values C₁, C₂,…C_n, so that C_i neighbors C_i-1 and C_i+1, for any i between 2 and n-1. Also, C₁ neighbors C_n and C₂, and C_n neighbors C_n-1 and C₁.
Finally, he set the criteria as per which he would choose that would remain his friends from now on. His purpose is to obtain a maximum value S, by summing up the individual qualities of the persons he selects. Positioning on the friend circle wasn't done randomly: Adisor seated nearby friends with similar behavior, so that he would never choose two people located on consecutive positions in the circle.
Help Adisor select his future friends, so that the above restrictions are respected.

Task

Write a program that determines positive integer S, representing the largest value that can be obtained by summing up the values of the "quality" of all persons that will continue to remain friends with Adisor.

Input Data

File friends.in contains on the first line a positive integer n representing the number of friends Adisor has. Starting with the second line we find n positive integers C₁, C₂, … C_n, one per line, representing in order the values of the "qualities" of each person.

Output Data

File friends.out will contain a single line, which will display positive integer S, with the meaning above.

Restrictions

• 1 < n <= 25000
• -2000 <= C₁, C₂, ... C_n <= 2000
• Adisor has at least one friend with C_i>0.
  

Example