[NOI Online 提高组]最小环(民间数据)

题目描述

给定一个长度为 $n$ 的正整数序列 $a_i$,下标从 $1$ 开始编号。我们将该序列视为一个首尾相邻的环,更具体地,对于下标为 $i$, $j(i \leqslant j)$ 的两个数 $a_i$, $a_j$,它们的距离为 $\min(j-i, i+n-j)$。 现在再给定 $m$ 个整数 $k_1$, $k_2$,..., $k_m$,对每个 $k_i(i=1$, $2$,..., $m)$,你需要将上面的序列 $a_i$ 重新排列,使得环上任意两个距离为 $k_i$ 的数字的乘积之和最大。

输入输出格式

输入格式


第一行两个正整数 $n$, $m$,表示序列长度与询问数。 接下来一行 $n$ 个正整数表示 $a_i$。 接下来 $m$ 行每行一个非负整数表示 $k_i$。

输出格式


共 $m$ 行,每行一个整数表示答案。

输入输出样例

输入样例 #1

6 4
1 2 3 4 5 6
0
1
2
3

输出样例 #1

91
82
85
88

说明

#### 输入输出样例 1 解释 - $k=0$ 时:答案为每个数平方的和。 - $k=1$ 时:一种最优方案:$\{3,1,2,4,6,5\}$。答案为 $3 \times 1 + 1 \times 2 + 2 \times 4 + 4 \times 6 + 6 \times 5 + 5 \times 3 = 82$。 - $k=2$ 时:一种最优方案:$\{3,6,1,4,2,5\}$。答案为 $3 \times 1 + 1 \times 2 + 2 \times 3 + 6 \times 4 + 4 \times 5 + 5 \times 6 = 85$。 - $k=3$ 时,一个合法的排列是 $1,5,3,2,6,4$ ,答案为 $88$。注意这里答案不是 $44$。 --- #### 数据范围与提示 对于所有测试数据:$1 \leqslant m \leqslant n \leqslant 2 \times 10^5$,$0 \leqslant k \leqslant \lfloor n/2\rfloor$,$1 \leqslant a_i \leqslant 10^5$。 | 测试点编号 | $n \leqslant$ | 特殊性质| | :--- | :--- | :--- | | 1 | $10$ | 无 | | 2 | $18$ | 无 | | 3 | $36$ | $n$ 为偶数且 $m=1$,$k=2$ | | 4,5 | $1000$ | $m \leqslant 10$,$k=1$ | | 6 | $50$ | $m \leqslant 10$,$k \leqslant 2$ | | 7,8 | $3000$ | 无 | | 9,10 | $2 \times 10^5$ | 无 |