[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$。

对于这样一个变换，所需代价定义为$TransformCost(X, Y) = \sum_{i = 1}^{n}{|\delta_i|}$

本题的任务即为寻找一个变换，使得$TransformCost(X, Y)$最小化。

输入格式

输入文件 sequence.in 包含两行。第一行 $4$ 个整数， $N, Q, A, B$。接下来一行包含 $N$ 个整数，分别为 $X_1, X_2, X_3, ... , X_n$ 。

输出格式

输出文件 sequence.out 仅包含一行，为最小的$TransformCost(X, Y)$。

样例 #1

样例输入 #1

3 6 2 2
1 4 6

样例输出 #1

1

提示

样例说明

可以将序列变换为 $2\ 4\ 6$ 或者 $1\ 3\ 5$。前者变换代价为 $1$，后者为 $2$。因此最小$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$。