#P18039. Linked VERSE

Linked VERSE

Linked VERSE

题目描述

给定长度为 NN 的整数序列 AA,其中每个元素不小于 −1-1。对于一个参数 cc,执行以下过程:

初始 x=0x=0。依次处理 i=1,…,Ni=1,\ldots,N:

  • 若 Ai=−1A_i=-1,令 x←max⁡(0,x−c)x\gets\max(0,x-c);
  • 否则,令 x←x+Aix\gets x+A_i。

回答 QQ 个询问。第 ii 个询问给出参数 CiC_i,求使用 c=Cic=C_i 时,在整个过程中 xx 曾经达到的最大值。每个询问都从 x=0x=0 独立开始。

输入格式

第一行两个整数 N,QN,Q。

第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

接下来 QQ 行,第 ii 行一个整数 CiC_i。

1≤N,Q≤3×1051\le N,Q\le3\times10^5,−1≤Ai≤106-1\le A_i\le10^6,0≤Ci≤1060\le C_i\le10^6。

输出格式

输出 QQ 行,第 ii 行为第 ii 个询问的答案。

样例 1

输入:

20 11
50 100 50 100 0 200 -1 50 100 -1 200 -1 200 0 200 -1 200 200 -1 200
30
60
90
180
270
360
540
200
400
600
0

输出:

1700
1550
1400
950
570
500
500
850
500
500
1850