P16422 [IATI 2022] Reorder

You are given $N$ numbers $- v_1, v_2, \cdots, v_N$, and an integer $A$. You can do an unlimited number of swaps in the array by swapping $v_i$ and $v_{i+1}$ for a cost of $v_i + v_{i+1}$. The new array after the swap would then be $v_1, \cdots , v_{i+1}, v_i \cdots, v_N$. For a certain number $R$, your task it to find the minimum sum of the costs of your swaps and $(v_1 + v_2 + \cdots + v_R) \times A$. Given $Q$ queries and an $R_i$ for each of them, find the minimum cost you can achieve for each query. **All queries are independent.**

There are 3 integers on the first line: $N$ – the size of the array, $Q$ – the number of queries and $A$ – the coefficient $(v_1 + v_2 + \cdots + v_R)$ is multiplied by. The second line of the input contains $N$ positive integers $v_1, \cdots, v_N$ - the starting array. The last line holds the positive integers $R_1, \cdots, R_Q$.

On each of the $Q$ lines output the minimum cost for the corresponding query.

### Explanation of the examples **Example 1**: It is optimal to not swap any elements. The cost is then $(4 + 1) \times 5 = 25$. **Example 2**: We can first swap $4$ with $1$ and then $4$ with $2$: 4 **1** 2 3 **1** 4 2 3 1 2 4 3 The costs of the swaps are $4 + 1 = 5$ and $4 + 2 = 6$. Therefore, the total cost is $$ 5 + 6 + (1 + 2) \times 6 = 29. $$ ### Constraints - $1 \le Q, R_i \le N$ - $1 \le v_i, A \le 10^6$ ### Subtasks | No. | Additional constraints | < |Points | |:-:|:-:|:-:|:-:| | | $N$ | Other | | 1 | $\le 8$ | $Q = 1$ | 5 | | 2 | $\le 5000$ | $Q = 1$ | 10 | | 3 | $\le 10^6$ | $Q = 1$ | 25 | | 4 | $\le 1.5 \times 10^4$ | – | 10 | | 5 | $\le 5 \times 10^4$ | – | 50 |