Owen had been through unrequited love with N MM for a long time. In order to celebrate the 8th anniversary of ZOJ, he decided to "watch white".
One night, MMs are sitting in a ring. Owen's plan is to give them love letters secretly so that MMs who receive letters will know that Owen loves them. Besides, each MM has a "happy point". The greater it is, the happier Owen will be if that MM receives his love letter.
One more problem. MM is very sensitive, so she will know if Owen (even secretly) drops a letter to the girl next to her. Meanwhile, MM is likely to be jealous. If she receives the love letter and finds that some other girl also gets a love letter, she will pia Owen to death.
Owen, as a smart boy, won't let MM pia him, and decides to program to calculate the maximum sum of happy points he can get. However, love is blind. Poor Owen has lost the ability to program. So he turns to you.
Input
There are no more than 10 test cases.
Each test case begins with an integer N (1 <= N <= 1000000).
Then followed N integers(0<= Ni <= 1000), each representing a happy point for one MM. The first and last MM sit next to each other, forming a ring.
Each test case occupies one line.
Output
One line for each test case.
An interger for each line indicating the maximum sun of happy points Owen can get.
Sample Input
5 1 2 3 4 5
6 1 2 3 4 5 6
Sample Output
8
12
