3out1in

Given an array B containing M (where M is odd) integers, you have to perform the following operation on B until it consists of only a single element.

• Choose distinct indices i, j, k of the array B.
• Remove 𝐵𝑖,𝐵𝑗,𝐵𝑘​ from the array.
• Append (𝐵𝑖+𝐵𝑗−𝐵𝑘).

Note that the operation reduces the length of B by 2.

For example, if 𝐵=[2,5,3,4,2], you can choose indices (3,1,4), delete the values 𝐵3,𝐵1,𝐵4 from B, and append 𝐵3+𝐵1−𝐵4=3+2−4=1 to it, obtaining 𝐵=[5,2,1].

Your aim is to maximize the value of the final element remaining in the array.

Let this maximum value be 𝑓(𝐵)

You are given an array A of length N. Answer Q queries on it.

In the i-th query, you are given an integer Ki​, which is guaranteed to be odd.

Compute 𝑓([𝐴1,𝐴2,…,𝐴𝐾𝑖]).

That is, compute the answer when considering only the first Ki​ elements of A.

Each query is independent, so the array remains unchanged across queries.