题目描述

给定 $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$ 行，每行输出对应询问的最小总代价。

4 1 5
4 1 2 3
2

25

4 1 6
4 1 2 3
2

29

提示

样例解释

样例 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$。因此总代价为

数据范围

• $1 \le Q, R_i \le N$
• $1 \le v_i, A \le 10^6$

子任务

翻译由 DeepSeek V4 Pro 完成