AT_abc403_g.[ABC403G] Odd Position Sum Query

初始有一个空数列 $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 完成