Minimum Adjustment Energy in Note Triples

In a musical sequence, there are n notes. The i-th note from the left has pitch \(s_i\). For any triple of notes \((s_i,s_j,s_k)\) with \(1\le i<j<k\le n\), it is observed that the three notes sound unpleasant. To remedy this, the notes are adjusted to \(s_i'\), \(s_j'\), \(s_k'\) respectively so that the restrictions \(s_i' \le s_k'\) and \(s_j' \le s_k'\) are satisfied.

The energy cost required to adjust each note is defined as follows:

• Changing \(s_i\) to \(s_i'\) costs \(a\times|s_i-s_i'|\).
• Changing \(s_j\) to \(s_j'\) costs \(b\times|s_j-s_j'|\).
• Changing \(s_k\) to \(s_k'\) costs \(c\times|s_k-s_k'|\).

Thus, the energy cost for adjusting the three notes is given by:

[ z = a\cdot|s_i-s_i'|+ b\cdot|s_j-s_j'|+ c\cdot|s_k-s_k'|. ]

For each triple \((i,j,k)\), let \(f(i,j,k)\) be the minimum possible energy cost when the optimal choices \((s_i',s_j',s_k')\) are made subject to the conditions \(s_i'\le s_k'\) and \(s_j'\le s_k'\). Your task is to compute the sum of \(f(i,j,k)\) over all triples with \(1\le i<j<k\le n\), modulo \(2^{32}\).

Hint: For a given triple of notes with pitches \(s_i, s_j, s_k\), the optimal adjustments can be derived by choosing an appropriate target value \(z\) for \(s_k'\) and by setting \(s_i'\) and \(s_j'\) to their original values if possible, or to \(z\) if they exceed \(z\). In particular, the minimum cost is given by the minimum of the following three candidate costs evaluated at \(z = s_i\), \(z = s_j\), and \(z = s_k\):

[ \begin{array}{rcl} \text{Candidate 1: } & & b\cdot\max(0, s_j-s_i) + c\cdot|s_k-s_i|,\[6pt] \text{Candidate 2: } & & a\cdot\max(0, s_i-s_j) + c\cdot|s_k-s_j|,\[6pt] \text{Candidate 3: } & & a\cdot\max(0, s_i-s_k) + b\cdot\max(0, s_j-s_k). \end{array} ]

Then, \(f(i,j,k)\) equals the minimum of these three. Finally, output the sum of \(f(i,j,k)\) for all valid triples modulo \(2^{32}\).

inputFormat

The input consists of two lines. The first line contains four integers: n a b c, where n is the number of notes, and a, b, c are positive integers representing the energy coefficients for adjusting notes i, j, and k, respectively.

The second line contains n integers: s_1 s_2 ... s_n, where s_i represents the pitch of the i-th note.

outputFormat

Output a single integer, the sum of \(f(i,j,k)\) over all \(1\le i<j<k\le n\), taken modulo \(2^{32}\) (i.e. modulo 4294967296).

sample

3 1 1 1
1 2 3

0