28480번 - Reorder 서브태스크다국어

문제

You are given $N$ numbers – $v_1, v_2, \dots , 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 $v1, \dots , v_{i+1}, v_i , \dots , 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, v_2, \dots , v_N$ - the starting array. The last line holds the positive integers $R_1, \dots , R_Q$.

출력

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

제한

• 1ドル ≤ Q, R_i ≤ N$
• 1ドル ≤ v_i , A ≤ 10^6$

서브태스크

힌트

Example No1: It is optimal to not swap any elements. The cost is then $(4 + 1) \times 5 = 25$.

Example No2: We can first swap 4ドル$ with 1ドル$ and then 4ドル$ with 2ドル$:

• $\color{red}{4}$ $\color{red}{1}$ 2ドル$ 3ドル$
• 1ドル$ $\color{red}{4}$ $\color{red}{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$.