Given a sequence of integers $X_1, X_2, X_3, \dots, X_n$ and three positive integers $Q, A, B$ satisfying:

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

For any $1 \le i \le n$, perform the following transformation: $Y_i = X_i + \Delta_i$, where $\Delta_i$ is an integer. The new sequence $Y$ must satisfy the following properties:

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

For such a transformation, the required transformation cost is defined as:

$$TransformCost(X, Y) = \sum_{i=1}^n |\Delta_i|$$

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

Input

The input contains two lines. The first line contains four integers $N, Q, A, B$. The next line contains $N$ integers, which are $X_1, X_2, X_3, \dots, X_n$.

Output

The output contains a single line, which is the minimum $TransformCost(X, Y)$.

Examples

Input 1

3 6 2 2
1 4 6

Output 1

1

Note

The sequence can be transformed into $2, 4, 6$ or $1, 3, 5$. The transformation cost for the former is $1$, and for the latter is $2$. Therefore, the minimum $TransformCost$ is $1$.

Constraints

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