题目描述

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

输入格式

第一行四个整数$n,Q,A,B$

第二行$n$个整数$X_i$

输出格式

一行一个整数，最小的$TransformCost(X,Y)$

样例

输入

3 6 2 2

1 4 6

输出

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