题目描述

给定一个整数序列 $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)$ 最小化。

输入格式

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

输出格式

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

3 6 2 2
1 4 6

1

提示

样例说明

可以将序列变换为 $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$。