AT_abc403_g [ABC403G] Odd Position Sum Query

[problemUrl]: https://atcoder.jp/contests/abc403/tasks/abc403_g 初始有一个空数列 $A$。 需要依次处理 $Q$ 个查询。第 $i$ 个查询的描述如下： > 给定整数 $y_i$。定义 $z$ 为：当 $i=1$ 时 $z=0$，否则 $z$ 为第 $i-1$ 个查询的答案。然后定义 $x_i=((y_i+z)\bmod 10^9)+1$。将 $x_i$ 添加到 $A$ 的末尾。 > > 接着，将 $A$ 升序排列得到序列 $B=(B_1,B_2,\ldots,B_i)$，求 $B$ 中奇数位置元素的总和。即若 $m$ 为不超过 $i$ 的最大奇数，则求 $B_1+B_3+B_5+\ldots+B_m$。

输入通过标准输入给出，格式如下： > $Q$ > $y_1$ > $y_2$ > $\vdots$ > $y_Q$

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

### 约束条件 - $1 \leq Q \leq 3 \times 10^5$ - $0 \leq y_i < 10^9$ - $1 \leq x_i \leq 10^9$ - 输入均为整数 ### 样例解释 #1 - 第 1 个查询：$y_1=1,z=0$，故 $x_1=((1+0)\bmod 10^9)+1=2$。$A$ 变为 $(2)$，排序后 $B=(2)$，答案为 $B_1=2$。 - 第 2 个查询：$y_2=3,z=2$，故 $x_2=((3+2)\bmod 10^9)+1=6$。$A$ 变为 $(2,6)$，排序后 $B=(2,6)$，答案为 $B_1=2$。 - 第 3 个查询：$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$。 - 第 4 个查询：$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 $x_1,x_2,\ldots,x_8$ 的值依次为： - 105282054 - 800516877 - 573289179 - 26509423 - 168629803 - 696409999 - 656737335 - 915059758 翻译由 DeepSeek V3 完成