P8475 "GLR-R3" Rainwater

  "The sky will turn to rain to soothe the clear scenery, and budding life waits for green fields." ---   Even though she kept saying in front of Tianyi that she was used to it, it had only been a few days since school started, and the pressure of cultural classes and band training still gave Ayling a headache.   All compressed into a weekend night. Standing on the balcony, she groped for the city’s outline blurred within the sound of rain. The rain on a Rainwater day, for the high-rise buildings in front of her—probably could hardly bring out any special mood.   "The rain of the Rainwater solar term, the dew of the White Dew solar term, the frost of the Frost’s Descent solar term, the snow of the Light Snow solar term, each twelve qian..."   Thinking messily, Ayling let out a snort of laughter. "But no matter where it is, the air in the rain, the first sunlight after the rain, is always so fresh that it makes people happy." Smiling at the curtain of rain, she fiddled with the old guitar in her hands, and without noticing, she began humming that song. ---   **Rainwater** "Waiting for the temperature of cool rain, to balance out the restless heat, searching for the twists of the wind."

The door behind them was knocked. After taking a big box of succulents that Tianyi brought back, and after setting things down and cuddling for a while, they decided to line up the succulents in a row on the balcony. The succulents have different heights. Tianyi first arranged a total of $n$ pots of succulents in a row at random, where the height of the $i$-th pot from left to right is $a_i$. For aesthetics, she hopes to swap the positions of some succulents so that the sequence $A$ formed by the heights has the smallest possible **lexicographical order**. However, to take care of the succulents’ feelings (?) she requires that Ayling may only choose an **even-length subsequence** of $A$ (the length may be $0$), swap the $1$st and $2$nd pots in the subsequence, the $3$rd and $4$th... and then put them back to their original positions. The hard work is left to Ayling, and the thinking is left to you! Please tell Ayling: using the operation of choosing a subsequence **only once**, what is the lexicographically smallest new height sequence $A'$ she can obtain? #### Formal statement Given an integer sequence $A$ of length $n$, indexed from $1$. You may choose **any** natural number $k$ and a **subsequence** $P$ of the sequence $\lang 1,2,\dots,n\rang$ with length $2k~(k\in\mathbb N)$. For all $i=1,2,\dots,k$, swap the values of $A_{P_{2i-1}}$ and $A_{P_{2i}}$. Among all possible resulting sequences $A'$, find the one with the smallest **lexicographical order**. **Lexicographical order**: For sequences $A$ and $B$ of length $n$, we say $A$ is lexicographically smaller than $B$ if and only if: $$ \exists i\in[1,n], (\forall j\in[1,i), A_j=B_j)\land A_i

To reduce input time, the sequence $A$ will be generated inside your program using `xorShift128Plus` and the provided seeds. Below is a sample program in C++: ```cpp #include // scanf const int MAXN = 712; // Set a right value according to your solution. int n, a[MAXN + 1]; namespace Generator { unsigned long long k1, k2; int thres; inline unsigned long long xorShift128Plus() { unsigned long long k3 = k1, k4 = k2; k1 = k4, k3 ^= (k3 > 17) ^ (k4 >> 26); return k2 + k4; } inline void generate() { for (int i = 1; i

To reduce output time, your program should output one integer on one line, representing the value of $\left(\sum_{i=1}^ni\times A_i'\right)\bmod2^{64}$.

#### Explanation for Sample #1 The generated sequence is $A=\lang 1,1,3,0,0,1,3\rang$. Choose $k=1,P=\lang 1,5\rang$, and the resulting sequence is $A'=\lang 0,1,3,0,1,1,3\rang$. Compute as required, and the answer is $43$. #### Explanation for Sample #2 The generated sequence is $A=\lang 2,8,0,6,2,2,1,7,8,3\rang$. Choose $k=3,P=\lang 1,3,4,7,8,10\rang$, and the resulting sequence is $A'=\lang 0,8,2,1,2,2,6,3,8,7\rang$. Compute as required, and the answer is $256$. ### Constraints and Notes **This problem uses Subtasks for scoring.** For $100\%$ of the testdata: $1\le n\le10^7$, $2\le \textit{thres}\le10^9$, $0\le k_1,k_2