AT_abc403_g [ABC403G] Odd Position Sum Query

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 $ .

The input is given from Standard Input in the following format: > $ Q $ $ y_1 $ $ y_2 $ $ \vdots $ $ y_Q $

Print $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 - 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 Explanation 2 Below are the values of $ x_1,x_2,\dots,x_8 $ in order: ``` 105282054 800516877 573289179 26509423 168629803 696409999 656737335 915059758 ``` ### 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.