Mae is a greedy lad. In the holy land of Greece, he was offered a contiguous stream of candies. Each offering had a different number of candies, so at the end he had to choose which offering to finally keep. But once a new offering has been made, he can either choose the current offering or keep the previously chosen one. Tell us, what is the maximum number of candies that he can grab at the end of the offered stream of candies.
Input: The first line contains the number of offerings (N) in the stream. Followed by this is the line which contains the number of candies in each offering (xi) separated by a space.