P4272 [CTSC2009] 序列变换

给定一个整数序列 $X_1, X_2, X_3, ... ,X_n$ 和三个正整数 $Q, A, B$ 满足： - $1 \leq X_i \leq Q$ 对于任意 $1 \leq i \leq n$； - $X_i \leq X_{i+1}$ 对于任意 $1 \leq i < n$； - $A \leq \frac{Q-1}{n-1}$ 且 $A \leq B$。 对于任意 $1 \leq i \leq n$，做如下变换：$Y_i = X_i + \delta_i$，其中 $\delta_i$ 是一个整数。使得新序列 $Y$ 满足如下性质： - $1 \leq Y_i \leq Q$ 对于任意 $1 \leq i \leq n$； - $Y_{i+1} - Y_i \in [A, B]$ 对于任意 $1 \leq i < n$。 对于这样一个变换，所需代价定义为 $\operatorname{TransformCost}(X, Y) = \sum_{i = 1}^{n}{\left\lvert\delta_i\right\rvert}$。 本题的任务即为寻找一个变换，使得 $\operatorname{TransformCost}(X, Y)$ 最小化。

无

无

### 样例说明 可以将序列变换为 $2\ 4\ 6$ 或者 $1\ 3\ 5$。前者变换代价为 $1$，后者为 $2$。因此最小 $\operatorname{TransformCost}$ 为 $1$。 ### 数据规模 对于 $10\%$ 的数据 , $N \leq 100, Q \leq 10000, 1\leq A, B \leq 100$。 对于 $30\%$ 的数据 , $N \leq 10000, Q \leq 10000, 1\leq A, B \leq 100$。 对于 $60\%$ 的数据 , $N \leq 10000, Q \leq 10^9, 1\leq A, B \leq Q$。 对于 $100\%$ 的数据, $N \leq 500000, Q \leq 10^9, 1\leq A, B \leq Q$。