/ 
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
空の数列 A があります。
Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。
整数 y_i が与えられる。 z を i=1 のときは 0、それ以外のときは i-1 番目のクエリに対する答えとし、 x_i を x_i=((y_i+z)\bmod 10^9)+1 で定義する。A の末尾に x_i を追加する。
その後、A を昇順に並べた列を B=(B_1,B_2,\ldots,B_i) としたとき B の奇数番目の要素の総和を求めよ。すなわち、i 以下の最大の奇数を m としたとき B_1+B_3+B_5+\ldots+B_m を求めよ。
制約
- 1\leq Q\leq 3\times 10^5
- 0\leq y_i\lt 10^9
- 1\leq x_i\leq 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
- 1 つ目のクエリについて、y_1=1,z=0 であるため x_1=((1+0)\bmod 10^9)+1=2 です。A の末尾に x_1 を追加すると A=(2) となります。A を昇順に並べた列 B は B=(2) であるため、求める値は B_1=2 です。
- 2 つ目のクエリについて、y_2=3,z=2 であるため x_2=((3+2)\bmod 10^9)+1=6 です。A の末尾に x_2 を追加すると A=(2,6) となります。A を昇順に並べた列 B は B=(2,6) であるため、求める値は B_1=2 です。
- 3 つ目のクエリについて、y_3=1,z=2 であるため x_3=((1+2)\bmod 10^9)+1=4 です。A の末尾に x_3 を追加すると A=(2,6,4) となります。A を昇順に並べた列 B は 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 の末尾に x_4 を追加すると A=(2,6,4,3) となります。A を昇順に並べた列 B は 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 の末尾に x_5 を追加すると A=(2,6,4,3,1000000000) となります。A を昇順に並べた列 B は 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,\ldots,x_8 の値は順に以下の通りです。
105282054 800516877 573289179 26509423 168629803 696409999 656737335 915059758
Score : 600 points
Problem Statement
There is an initially empty sequence A.
You are given Q queries to process in order. The i-th query is explained below:
You are given an integer y_i. If i=1, let z be 0; otherwise, let z be the answer to the (i-1)-th query. Define x_i=((y_i+z)\bmod 10^9)+1. Append x_i to the end of A.
Then, let B=(B_1,B_2,\ldots,B_i) be the sequence A sorted in ascending order, and find the sum of the odd-indexed elements of B. That is, find B_1 + B_3 + B_5 + \dots + B_m, where m is the largest odd number not exceeding i.
Constraints
- 1 \le Q \le 3\times 10^5
- 0 \le y_i < 10^9
- 1 \le x_i \le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Q y_1 y_2 \vdots y_Q
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
5 1 3 1 999999994 999999993
Sample Output 1
2 2 8 6 1000000006
- For the 1st query, y_1=1, z=0, so x_1=((1+0)\bmod 10^9)+1=2. Appending this to the end of A gives A=(2). Sorting A in ascending order yields B=(2), and the sought value is B_1=2.
- For the 2nd query, y_2=3, z=2, so x_2=((3+2)\bmod 10^9)+1=6. Appending gives A=(2,6), so B=(2,6) and the sought value is B_1=2.
- For the 3rd query, y_3=1, z=2, so x_3=((1+2)\bmod 10^9)+1=4. Appending gives A=(2,6,4), so B=(2,4,6) and the sought value is B_1+B_3=8.
- For the 4th query, y_4=999999994, z=8, so x_4=((999999994+8)\bmod 10^9)+1=3. Appending gives A=(2,6,4,3), so B=(2,3,4,6) and the sought value is B_1+B_3=6.
- For the 5th query, y_5=999999993, z=6, so x_5=((999999993+6)\bmod 10^9)+1=1000000000. Appending gives A=(2,6,4,3,1000000000), so B=(2,3,4,6,1000000000) and the sought value is B_1+B_3+B_5=1000000006.
Sample Input 2
8 105282053 695234822 468007124 120710491 568831200 700753895 765188109 262666319
Sample Output 2
105282054 105282054 905798931 599798602 995656103 891549225 1652393438 1652393438
Below are the values of x_1,x_2,\dots,x_8 in order:
105282054 800516877 573289179 26509423 168629803 696409999 656737335 915059758