410297: GYM104003 E William and Robot

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.

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 the maximum score William can achieve.

4
6 1 1 4

10

10
1 3 4 9 5 2 5 5 3 6

30