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:
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.
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 si, the number of strawberries on the i'th pavlova (0 ≤ si ≤ 1,000,000).
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 232, 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.
8 3 3 2 2 3 4 3 5
3 1 2 4