Description

In the note sequence Aling is adjusting is $n$ notes in total. The $i$-th note from the left has a pitch of $s_i$. Aling discovered that three of the notes $s_i,s_j,s_k~(1\le i<j<k\le n)$ is bad to listen to, thus she decided to change them into $s_i',s_j',s_k'$, where $s_i'\le s_k'$ and $s_j'\le s_k'$. However, operating on a touchpad is tough:

• Adjusting $s_i$ to $s_i'$ takes her $a\times|s_i-s_i'|$ points of energy.

• Adjusting $s_j$ to $s_j'$ takes her $b\times|s_j-s_j'|$ points of energy.

• Adjusting $s_k$ to $s_k'$ takes her $c\times|s_k-s_k'|$ points of energy.

Therefore, to finish the adjusting work on all the three notes, the points of energy she need is:

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

Aling surely will find $(s_i',s_j',s_k')$ that makes $z$ minimum. Let $f(i,j,k)$ denote the minimum $z$. Aling now wants to know the sum over all the $f(i,j,k)$s that $i<j<k$. You're only required to output the ans modulo $2^{32}$.

Input Format

The first line of input contains an integer $n$ — the length to the note sequence.

The second line of input contains three integers $a,b,c$ — the mentioned constants in the description.

The third line od input contains $n$ integers $s_i$ — the pitch of each note.

Output Format

One integer — the remainder of the sum over all the $f(i,j,k)$s that $i<j<k$.

4
3 4 5
2 4 3 1

39

Hint

Sample Explanation

$f(1,2,3)=4$, one of the ideal $(s_i',s_j',s_k')$s is $(2,3,3)$.

$f(1,2,4)=13$, one of the ideal $(s_i',s_j',s_k')$s is $(2,2,2)$.

$f(1,3,4)=9$, one of the ideal $(s_i',s_j',s_k')$s is $(2,2,2)$.

$f(2,3,4)=13$, one of the ideal $(s_i',s_j',s_k')$s is $(3,3,3)$.

The sum of the $f(i,j,k)$s is $4+13+9+13=39$.

Constraints

Subtasks Applied. You can only gain the score of the subtask if you accepted all the tests in the subtask.

Subtask ID	$n$	Special Property	Score
$1$	$=3$	No	$5$
$2$	$\le300$
$3$	$\le900$		$10$
$4$	$\le3\times10^3$		$20$
$5$	$\le5\times10^4$
$6$	$\le5\times10^5$	Yes
$7$		No

Special Property: the quantity of different pitches is at most $10$.(i.e. there is at most 10 kinds of pitches.)

For all tests, it is guaranteed that $3\le n\le5\times10^5$，$1\le s_i,a,b,c\le 10^9$.