U188872 可持久化摸鱼

这并不是数据结构题。原题 SDFZ-NOIP2021模拟11-T2。

$\text{zyd}$ 和 $\text{lyn}$ 在河边摸鱼，摸完之后分鱼。规则如下： 首先给 $n$ 条鱼编号 $1,...,n$ ，设它们的斤两为正整数 $a_1,...,a_n$。给定一个数字 $p$，满足 $1\le p\le n$，执行如下操作： - 将 $a_1,...,a_{p-1}$ 放到两个人的中间（其余的放到一边）； - 将 $a_p$ 放到两个人的中间，然后由 $\text{zyd}$ 从中间的鱼中选一条拿走； - 将 $a_{p+1}$ 放到两个人的中间，然后由 $\text{lyn}$ 从中间的鱼中选一条拿走； - 将 $a_{p+2}$ 放到两个人的中间，然后由 $\text{zyd}$ 从中间的鱼中选一条拿走； - 将 $a_{p+3}$ 放到两个人的中间，然后由 $\text{lyn}$ 从中间的鱼中选一条拿走…… - 将 $a_{n}$ 放到两个人的中间，然后由一人 $A$ 从中间的鱼中选一条拿走； - 另一人 $B$ 从中间的鱼中选一条拿走； - 另一人 $A$ 从中间的鱼中选一条拿走； - 另一人 $B$ 从中间的鱼中选一条拿走…… 直到中间没有鱼。 这里如果 $n-p$ 是偶数，那么 $A$ 代指 $\text{zyd}$， $B$ 代指 $\text{lyn}$。否则 $A,B$ 互换。 $\text{zyd}$ 想知道，在他俩都绝顶 ~~摸鱼~~ 聪明（并且都希望自己分得鱼的斤两尽量大）的情况下，$\text{zyd}$ 能获得的鱼的斤两之和最大是多少？ 为了强行增加题目难度，所以有 $k$ 次询问，每次询问一个 $p$ ，要求你得到答案。

第一行两个正整数 $n,k$； 接下来一行 $n$ 个正整数 $a_1,...,a_n$； 接下来 $k$ 行每行一个整数表示询问一个 $p$。

$k$ 行，每行一个整数表示答案。

#### 样例解释 对于 $p=3$：一开始中间有 $3,4$。 再加入 $5$，可见 $\text{zyd}$ 最优策略是拿走一个 $5$，剩下 $3,4$； 再加入 $5$，可见 $\text{lyn}$ 最优策略是拿走一个 $5$，剩下 $3,4$； 再加入 $1$，可见 $\text{zyd}$ 最优策略是拿走一个 $4$，剩下 $1,3$； 可见 $\text{lyn}$ 会拿走 $3$，剩下 $1$ 被 $\text{zyd$ 拿走，这样 $\text{zyd}$ 最大能摸到斤两和为 $10$ 的鱼。 #### 数据范围 对于 $30\%$ 的数据，$n,k\le 200$； 对于 $50\%$ 的数据，$n,k\le 2000$； 存在另外 $20\%$ 的数据，$a_i\le 2$； 另有 $50\%$ 的数据，$1\le n\le 10^5,1\le k\le 1000,1\le a_i\le n$。