CF1916C Training Before the Olympiad

Masha and Olya have an important team olympiad coming up soon. In honor of this, Masha, for warm-up, suggested playing a game with Olya: There is an array $ a $ of size $ n $ . Masha goes first, and the players take turns. Each move is described by the following sequence of actions: $ \bullet $ If the size of the array is $ 1 $ , the game ends. $ \bullet $ The player who is currently playing chooses two different indices $ i $ , $ j $ ( $ 1 \le i, j \le |a| $ ), and performs the following operation — removes $ a_i $ and $ a_j $ from the array and adds to the array a number equal to $ \lfloor \frac{a_i + a_j}{2} \rfloor \cdot 2 $ . In other words, first divides the sum of the numbers $ a_i $ , $ a_j $ by $ 2 $ rounding down, and then multiplies the result by $ 2 $ . Masha aims to maximize the final number, while Olya aims to minimize it. Masha and Olya decided to play on each non-empty prefix of the initial array $ a $ , and asked for your help. For each $ k = 1, 2, \ldots, n $ , answer the following question. Let only the first $ k $ elements of the array $ a $ be present in the game, with indices $ 1, 2, \ldots, k $ respectively. What number will remain at the end with optimal play by both players?

N/A

N/A

In the third test case, for a prefix of length $ 1 $ , the answer is $ 3 $ . For a prefix of length $ 2 $ , Masha has only one move, so the answer is $ 12 $ . For a prefix of length $ 3 $ , Masha has three possible moves: she chooses $ 3 $ and $ 10 $ , then the final number is $ 22 $ , $ 3 $ and $ 11 $ , then the final number is $ 24 $ , $ 10 $ and $ 11 $ , then the final number is $ 22 $ , so Masha will choose $ 3 $ and $ 11 $ and get $ 24 $ .