(classical problem, this choice of constraints is due to PA10)

n (n <= 1,000,000) herds of cows (at most 10^9 cows in a herd) are standing along a fence, and two ranchers take turns claiming (and removing) herds from the two ends of this sequence. If both ranchers play perfectly to maximize their cow count, find the end result.

Brief and incomplete history of this problem:

* This is often found as a standard exercise in dynamic programming
* It appeared as IOI'96 Day 1 Problem 1: A Game
* Subsequently things like this with bounds n <= 1,000 showed up in almost every country's national selections, and is considered a 'standard' problem by now.
* At some point, Tomasz Idziaszek was kicked by a donkey (CHN contestants' colloquialism for epiphanies that lead to wtm problems) and came up with an O(nlogn) time algorithm for it.
* The approach was so ridiculous that when this problem was given on PA, the statement was modified to hint strongly at the solution.
* The contest happened over a weekend, only 3 Tomeks solved it.