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

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.

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

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^{32}, 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

10

3 1 2 4

0

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

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 26 October 2021, 1:16am AEDT