P16422 [IATI 2022] Reorder

给定 $N$ 个数 $v_1, v_2, \cdots, v_N$ 和一个整数 $A$。你可以进行无限次相邻交换操作：交换 $v_i$ 与 $v_{i+1}$ 的费用为 $v_i + v_{i+1}$。交换后得到的新数组为 $v_1, \cdots , v_{i+1}, v_i, \cdots, v_N$。对于某个确定的数 $R$，你的任务是求出所有交换操作的费用总和加上 $(v_1 + v_2 + \cdots + v_R) \times A$ 的最小值。现给出 $Q$ 个询问，每个询问给出对应的 $R_i$，你需要对每个询问求出所能达到的最小总代价。**所有询问相互独立。**

第一行有三个整数：$N$ —— 数组大小，$Q$ —— 询问个数，以及 $A$ —— $(v_1 + v_2 + \cdots + v_R)$ 所乘的系数。 第二行包含 $N$ 个正整数 $v_1, \cdots, v_N$ —— 初始数组。 第三行包含 $Q$ 个正整数 $R_1, \cdots, R_Q$。

共 $Q$ 行，每行输出对应询问的最小总代价。

### 样例解释 **样例 1**：最优策略是不进行任何交换。此时代价为 $(4 + 1) \times 5 = 25$。 **样例 2**：我们可以先将 $4$ 与 $1$ 交换，再将 $4$ 与 $2$ 交换： `4 1 2 3` → `1 4 2 3` → `1 2 4 3` 这两次交换的费用分别为 $4 + 1 = 5$ 和 $4 + 2 = 6$。因此总代价为 $$ 5 + 6 + (1 + 2) \times 6 = 29. $$ ### 数据范围 - $1 \le Q, R_i \le N$ - $1 \le v_i, A \le 10^6$ ### 子任务 | 编号 | 附加约束 | < | 分值 | |:----:|:-----------------------:|:-:|:----:| | | $N$ | 其他 | | | 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 | 翻译由 DeepSeek V4 Pro 完成