Processing math: 100%
Game on array - MarisaOJ: Marisa Online Judge

Game on array

Time limit: 1000 ms
Memory limit: 256 MB
Marisa and Reimu are playing a game on an array A of n integers. Starting from Marisa, they take turns performing the following move: - Pick either the first or the last element in array A and remove it. The player gain x points, where x is the previously chosen element. Let x and y are the score of Marisa and Reimu at the end of the game, respectively. Marisa wants to maximize x−y while Reimu wants to minimize x−y. Assuming they both play optimally, find the resulting x−y. ### Input - The first line contains an integer n. - The second line contains n integers Ai. ### Output - Print x−y. ### Constraints - 1≤n≤5000. - 1≤Ai≤109. ### Example Input: 410809030 Output: 10