Minimum Transformation Cost

Given a non-decreasing integer sequence \(X_1, X_2, \ldots, X_n\) such that \(1 \le X_i \le Q\) and three positive integers \(Q, A, B\) satisfying \(A \le \frac{Q-1}{n-1}\) and \(A \le B\), you are allowed to transform each element \(X_i\) into \(Y_i = X_i + \delta_i\) (where \(\delta_i\) is an integer) such that the new sequence \(Y\) obeys the following conditions:

1. \(1 \le Y_i \le Q\) for all \(1 \le i \le n\);
2. \(Y_{i+1} - Y_i \in [A, B]\) for all \(1 \le i < n\).

The transformation cost is defined as \(\operatorname{TransformCost}(X, Y) = \sum_{i=1}^{n} |\delta_i|\). Your task is to find a transformation that minimizes the total cost.

inputFormat

The input consists of two lines:

The first line contains four integers \(n\), \(Q\), \(A\), and \(B\), where \(n\) is the length of the sequence.

The second line contains \(n\) space-separated integers \(X_1, X_2, \ldots, X_n\) representing the original non-decreasing sequence.

outputFormat

Output a single integer representing the minimum transformation cost required to achieve the desired sequence properties.

sample

3 10 2 5
1 3 6

0