分数: 600 点
问题陈述
有一个最初为空的序列 A.
你被给予 Q 查询按顺序处理。的 i第一个查询解释如下:
给你一个整数 y_i。如果 i=1,让 z be 0;否则,让 z 是以下问题的答案 (i-1)第一个查询。定义 x_i=((y_i+z)\bmod 10^9)+1。追加 x_i 到年底 A.
然后,让 B=(B_1,B_2,\ldots,B_i) 是序列 A 按升序排序,并找到奇数索引元素的总和 B。也就是说,找到 B_1 + B_3 + B_5 + \dots + B_m,其中 m 为不超过的最大奇数 i.
约束
- 1 \le Q \le 3\times 10^5
- 0 \le y_i < 10^9
- 1 \le x_i \le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
Q y_1 y_2 \vdots y_Q
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i- 第一个查询。
示例输入 1
5 1 3 1 999999994 999999993
示例输出 1
2 2 8 6 1000000006
- 对于第一个查询, y_1=1, z=0,所以 x_1=((1+0)\bmod 10^9)+1=2。将此附加到末尾 A 给出 A=(2)。排序 A 按收益率升序排列 B=(2),求得的值为 B_1=2.
- 对于第二个查询, y_2=3, z=2,所以 x_2=((3+2)\bmod 10^9)+1=6。追加给出 A=(2,6),所以 B=(2,6) 并且寻求的值为 B_1=2.
- 对于第三个查询, y_3=1, z=2,所以 x_3=((1+2)\bmod 10^9)+1=4。追加给出 A=(2,6,4),所以 B=(2,4,6) 并且寻求的值为 B_1+B_3=8.
- 对于第四个查询, y_4=999999994, z=8,所以 x_4=((999999994+8)\bmod 10^9)+1=3。追加给出 A=(2,6,4,3),所以 B=(2,3,4,6) 并且寻求的值为 B_1+B_3=6.
- 对于第 5 个查询, y_5=999999993, z=6,所以 x_5=((999999993+6)\bmod 10^9)+1=1000000000。追加给出 A=(2,6,4,3,1000000000),所以 B=(2,3,4,6,1000000000) 并且寻求的值为 B_1+B_3+B_5=1000000006.
示例输入 2
8 105282053 695234822 468007124 120710491 568831200 700753895 765188109 262666319
示例输出 2
105282054 105282054 905798931 599798602 995656103 891549225 1652393438 1652393438
以下是以下值 x_1,x_2,\dots,x_8 按顺序:
105282054 800516877 573289179 26509423 168629803 696409999 656737335 915059758