Avançado Informática - Semana 23

Cartões

 

Dois jogadores, Alberto e Wanderley, disputam um jogo. Um conjunto com um número par de cartões contendo números inteiros é disposto sobre uma mesa, um ao lado do outro, formando uma sequência. Alberto começa, e pode pegar um dos dois cartões das pontas. Wanderley então pode pegar um dos dois cartões das pontas e novamente Alberto pode pegar um cartão das pontas, e assim por diante, até Wanderley pegar o último cartão.

Alberto, o primeiro a jogar, tem como objetivo maximizar o número total de pontos que ele con- segue, somando os valores dos cartões escolhidos. Wanderley, o segundo jogador, quer atrapalhar o Alberto e fazer com que ele consiga o menor número de pontos possível. Em suma, ambos querem fazer o melhor possível, Alberto querendo maximizar sua soma e Wanderley querendo minimizar a soma de Alberto.

Você deve escrever um programa que, dada a sequência de cartões, determine o maior número de pontos que Alberto consegue obter.

Entrada

Cada caso de teste é descrito em duas linhas. A primeira linha contém um inteiro par N (2 ≤ ≤ 104), que indica o número de cartões sobre a mesa. A segunda contém inteiros, que descrevem a sequência de cartões. Cada um dos inteiros cabem em um inteiro de 32 bits.

Saída

Para cada caso de teste seu programa deve imprimir uma única linha, contendo um único inteiro, o maior número de pontos que Alberto consegue obter.

Exemplo de Entrada Exemplo de Saída
4
0 -3 5 10
4
0 -3 5 7
4
47 50 -3 7
10
7
57