Problem: Nomnomnomnom: Can Has Dessert?

Want to try solving this problem? You can submit your code online if you log in or register.

Nomnomnomnom: Can Has Dessert?

Input File: nomin.txt
Output File: nomout.txt
Time Limit: 1 second
Memory Limit: 16 MB

The hippopotami of North Yorkshire have been keeping themselves busy since we last saw them. They still enjoy sunbathing, ballet dancing, and eating naughty children. Now, however, they have acquired a taste for dessert. Dessert is a very special treat, usually reserved for the eldest hippos of all: Bentor and Jonid.

Tonight, the respectful locals have presented the hippos with a line of pavlovas: delicious, moist and fresh from the oven. The two hippos will eat the pavlovas using the following system:

Bentor will eat the first B pavlovas on the road. Mmm!
Jonid will eat the next J pavlovas on the road. Scrumptious!
Any remaining pavlovas will be distributed amongst the younger hippopotami.

The pavlovas are covered in strawberries and cream; some have more than others. Bentor and Jonid both love strawberries but neither wishes to be seen as greedy. They agree that they will eat the same number of strawberries—i.e., the B pavlovas that Bentor eats must contain the same total number of strawberries as the J pavlovas that Jonid eats. Naturally, they would like to eat as many strawberries as possible in the process.

For example, consider the following line of pavlovas:

The hippos will start on the left of the line. Bentor will eat the first B, and then Jonid will eat the next J. In order for Bentor and Jonid to consume the most number of strawberries, Bentor should eat the first 4, and Jonid should eat the next 3. This gives them 10 strawberries each. This is the most strawberries they can fairly eat.

The hippos have heard many good things about IT. They believe that a computer program could assist them in their pavlova-eating. Unfortunately, they know nothing of programming. They have come to you to find out the greatest number of strawberries they can each eat while still avoiding accusations of greed.

Input

The first line of input contains a single integer N, the total number of pavlovas (1 ≤ N ≤ 1,000,000). The following N lines describe the long line of pavlovas in the order the hippos may eat them. The i'th of these lines contains a single integer s_i, the number of strawberries on the i'th pavlova (0 ≤ s_i ≤ 1,000,000).

Output

Your output must consist of a single integer representing the greatest number of strawberries that each of the hippos can eat. Note that this number may exceed 2³², so C/C++ users are advised to use the long long data type. Unfortunately, Pascal users are ineligible for free advice.

If it is not possible for the hippos to eat any pavlovas fairly, you should of course output 0.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Subtasks

For Subtask 1 (20 points), N ≤ 100.
For Subtask 2 (20 points), N ≤ 5,000.
For Subtask 3 (60 points), no further constraints apply.