P12809 [AMPPZ 2019] Cheese Game

**Time limit: 2s, memory limit: 512MB.**

After taking part in the annual _Two-player Games and Applied Cryptography Symposium_, Alice and Bob want to relax by playing their favourite game. They have arranged $n$ cheese slices in a row, numbered from $1$ to $n$. As we all know, though cheese is tasty in general, some slices can be better than others – this is why the $i$-th slice is described by its deliciousness $o_i$. Alice starts the game and the players alternate their moves. In a move, a player may eat any set of cheese slices that are still left on the board, providing that the set contains no two neighbouring slices (i.e. numbered $i$ and $i+1$ for any $1 \leq i \leq n - 1$). We assume that the numbers of the slices do not change, so during the game no new neighbouring pairs appear. Of course, both players aim to maximize the total deliciousness of their eaten pieces. Assuming that they both play optimally, what is the maximal score that Alice can achieve?

The first line of input contains the number of test cases $z$ ($1 \leq z \leq 20$). The test cases follow, each one in the following format: - The first line of a test case contains the number of cheese slices $n$ ($1 \leq n \leq 100\,000$). - The second line contains $n$ integers $o_1, o_2, \dots, o_n$ ($1 \leq o_i \leq 1\,000\,000$) – the values of the pieces’ deliciousness.

For every test case, output a single integer – the total deliciousness of the slices eaten by Alice, assuming that both players play optimally.