P4105 [HEOI2014] Light Catkins Piled All Over the Southern Garden

Xiao Z is a poetry enthusiast in the ZRP (Zombies’ Republic of Poetry). Recently, he has been studying the prosody of classical poetry. In the past, poems were meant to be sung to melodies. For example, consider the following tune of “Bodhisattva Man.” When sung, the corresponding notes are: ``` 南 园 满 地 堆 轻 絮， 愁 闻 一 霎 清 明 雨 1 1 5 5 6 6 5 4 4 3 3 2 2 1 ``` Therefore, one can see that the sequence of notes `1 1 5 5 6 6 5 4 4 3 3 2 2 1` becomes the key to studying prosody. From many historical sources, Xiao Z found that the pitch of an ancient tune is non-decreasing. He wants to know, for a given piece, how to raise or lower its notes to make the sequence non-decreasing, while making the largest adjustment among all notes as small as possible. That is, if a piece with $n$ notes is viewed as a positive integer sequence $A_1 \cdots A_n$, the goal is to find another positive integer sequence $B_1 \cdots B_n$ such that for every $1 \leq i < n$ we have $B_i \leq B_{i+1}$, and $\texttt{Ans} = \max\{\lvert A_j - B_j \rvert, 1 \leq j \leq n\}$ is minimized. Xiao Z quickly figured out a method, but since he is busy writing poetry, the task is handed over to you.

Since the testdata size may be large, the data are generated as follows. Each test consists of $7$ numbers: $n, S_a, S_b, S_c, S_d, A_1, \texttt{Mod}$, meaning there are $n$ notes and the first note is $A_1$. The generation rules are: define $F(x) = S_a \times x^3 + S_b \times x^2 + S_c \times x + S_d$; then the recurrence is $A_i = \bigl( F(A_{i-1}) + F(A_{i-2}) \bigr) \bmod \texttt{Mod}$, with $A_0 = 0$. Since intermediate values may be very large, at each step and for every number in $A$, take modulo $\texttt{Mod}$.

Output one line containing a positive integer $\texttt{Ans}$.

Constraints - For $10\%$ of the testdata, $n \leq 3$. - For $20\%$ of the testdata, $n \leq 10$. - For $30\%$ of the testdata, $n \leq 10^2$. - For $50\%$ of the testdata, $n \leq 10^3$. - For $70\%$ of the testdata, $n \leq 10^5$. - For $100\%$ of the testdata, $2 < n \leq 5 \times 10^6$, $S_a, S_b, S_c, S_d, A_1 \leq \min\{10^4, \texttt{Mod}\}$, $1 < \texttt{Mod} \leq 10^9 + 7$, and all input numbers are positive integers. Friendly hint In the sample, the generated sequence is $199, 4568, 1901$. If you change $4568$ to $3234$ and also change $1901$ to $3234$, the cost is $1334$. Translated by ChatGPT 5