Background

Have you tried to do attunement with the touchpad of a notebook?

Aling is playing Tianyi — 's newest X Studio voicebank. Due to the mysterious disappearance of her mouse, it takes an extreme effort for her to adjust every note......

Problem 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$.