P8927 "GMOI R1-T4" Rain

> **Praying for Rain** > > Grandpa Jade Emperor is also surnamed Zhang, > > so why are you making things hard for my Zhang *Chang? > > If it does not rain within three days, > > first I will tear down the Dragon King Temple, > > __then I will use cannons to blow up your mother.__ If it still does not rain, Marshal Zhang will blow up all religious sites across Asia! Because Hakurei Shrine can be seen from the outside world, it naturally cannot escape this either. Reimu is very anxious and plans to use her ancestral secret technique to pray for rain...

To prevent the shrine from being "blasted by cannons", Reimu needs to pray for rain. To pray for rain, she needs to build $n$ magic circles on a straight road, numbered $1,2,\cdots,n$. You are given an array $a$ of length $n$, meaning that the magic circles are built at positions $a_1$ to $a_n$. What you need to do is assign the numbers to the magic circles. Reimu needs to test the effect of the circles. She will walk from circle $1$ to circle $2$, from $2$ to $3$, and so on until she reaches circle $n$, then walk back from circle $n$ to circle $1$. Due to the special effect of the circles, the distance from the $i$-th to the $(i+1)$-th is $\left|a_i\times p-a_{i+1}\times q\right|$. In particular, the distance from circle $n$ back to circle $1$ is $\left|a_n\times p-a_1\times q\right|$. Here $p,q$ are two given constants, and $a_i,a_{i+1}$ are the positions of the two circles. Reimu wants you to find the maximum walking distance, and output a corresponding arrangement of the positions of circles numbered from $1$ to $n$. (If there are multiple answers, output any one.)

The first line contains an integer $n$, representing the number of magic circles. The second line contains two integers $p,q$, representing the multiplier constants. The third line contains $n$ integers, representing the array $a$.

The first line contains one integer, representing the answer. The second line contains $n$ integers, representing a permutation of the positions $a$, output in order from circle $1$ to circle $n$.

**This problem uses SPJ.** **The input size is large; it is recommended to use faster input methods.** For $100\%$ of the testdata, $10\le n\le 10^6$, $1\le p,q \le 10^{5}$, $1\le a_i\le 10^{5}$. | ID | $n$ | $p,q$ | $a_i$ | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $n=10$ | $p,q\le 10^{3}$ | $a_i\le 10^{3}$ | $4$ | | $2$ | $n=10$ | $p,q\le 10^{3}$ | $a_i\le 10^{3}$ | $5$ | | $3$ | $n=10$ | $p,q\le 10^{3}$ | $a_i\le 10^{3}$ | $5$ | | $4\sim 6$ | $n=19$ | $p,q\le 10^{5}$ | $a_i\le 10^{5}$ | $10$ | | $7$ | $n\le 10^{4}$ | $p,q\le 10^{5}$ | $a_i\le 10^{5}$ | $8$ | | $8$ | $n\le 10^{4}$ | $p,q\le 10^{5}$ | $a_i\le 10^{5}$ | $9$ | | $9$ | $n\le 10^{4}$ | $p,q\le 10^{5}$ | $a_i\le 10^{5}$ | $9$ | | $10\sim 12$ | $n\le 10^{6}$ | $p,q\le 10^{5}$ | $a_i\le 10^{5}$ | $10$ | Translated by ChatGPT 5