410297: GYM104003 E William and Robot

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. William and Robottime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

William is playing a game with a robot. In this game, there is an array of $$$n$$$ integers in a line, numbered $$$1, \ldots n$$$. $$$n$$$ is even.

William and the robot take turns selecting integers from the array, starting with William. William can take an integer from anywhere in the array as long as it has not already been taken by any player. The robot always takes the leftmost, untaken integer (i.e. the one with the lowest index). The game ends once all integers have been taken. William's score is the sum of his chosen integers.

Help William get the maximum score possible.

Input

The first line contains $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the number of integers in the array.

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), where $$$a_i$$$ denotes the $$$i$$$th integer of the array.

Output

Output the maximum score William can achieve.

ExamplesInput
4
6 1 1 4
Output
10
Input
10
1 3 4 9 5 2 5 5 3 6
Output
30

加入题单

算法标签: