Description

Given an integer sequence $X_1, X_2, X_3, \dots, X_N$ and three positive integers $Q, A, B$ that satisfy:

• $1 \leq X_i \leq Q$ for any $1 \leq i \leq N$;
• $X_i \leq X_{i+1}$ for any $1 \leq i < N$;
• $A \leq \frac{Q - 1}{N - 1}$ and $A \leq B$.

For any $1 \leq i \leq N$, perform the transformation $Y_i = X_i + \delta_i$, where $\delta_i$ is an integer, such that the new sequence $Y$ satisfies:

• $1 \leq Y_i \leq Q$ for any $1 \leq i \leq N$;
• $Y_{i+1} - Y_i \in [A, B]$ for any $1 \leq i < N$.

For such a transformation, the required cost is defined as $\operatorname{TransformCost}(X, Y) = \sum_{i = 1}^{N}{\left\lvert\delta_i\right\rvert}$.

The task is to find a transformation that minimizes $\operatorname{TransformCost}(X, Y)$.

Input Format

The first line contains $4$ integers $N, Q, A, B$.
The second line contains $N$ integers, namely $X_1, X_2, \dots, X_N$.

Output Format

Output a single line with the minimal $\operatorname{TransformCost}(X, Y)$.

3 6 2 2
1 4 6

1

Hint

Sample Explanation.

You can transform the sequence to $2\ 4\ 6$ or $1\ 3\ 5$. The former has a cost of $1$, and the latter has a cost of $2$. Therefore, the minimal $\operatorname{TransformCost}$ is $1$.

Constraints.

For $10\%$ of the testdata, $N \leq 100$, $Q \leq 10000$, $1 \leq A, B \leq 100$.
For $30\%$ of the testdata, $N \leq 10000$, $Q \leq 10000$, $1 \leq A, B \leq 100$.
For $60\%$ of the testdata, $N \leq 10000$, $Q \leq 10^9$, $1 \leq A, B \leq Q$.
For $100\%$ of the testdata, $N \leq 500000$, $Q \leq 10^9$, $1 \leq A, B \leq Q$.

Translated by ChatGPT 5