题目背景

为避免卡常，本题时限为比赛时的 2 倍。

你试过用笔记本的触摸板操作扒谱吗？

阿绫正在玩天依——最新的 X Studio 声库，由于触控板和鼠标神秘失踪，她每调整一个音符都极其费力……

题目描述

在阿绫正在调的序列中一共有 $n$ 个音符，从左至右第 $i$ 个音符的音高为 $s_i$。阿绫发现其中三个音符 $s_i,s_j,s_k~(1\le i<j<k\le n)$ 产生的听感不佳，她决定将它们调整为 $s_i',s_j',s_k'$，使得 $s_i'\le s_k'$ 且 $s_j'\le s_k'$。扒拉触摸板真的很难受：

• 调节 $s_i$ 到 $s_i'$ 需要耗费阿绫 $a\times|s_i-s_i'|$ 的精力；
• 调节 $s_j$ 到 $s_j'$ 需要耗费阿绫 $b\times|s_j-s_j'|$ 的精力；
• 调节 $s_k$ 到 $s_k'$ 需要耗费阿绫 $c\times|s_k-s_k'|$ 的精力。

于是，调节完这三个音符，阿绫耗费的精力为：

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

阿绫自然会找到使得 $z$ 值最小的 $(s_i',s_j',s_k')$，记此时的 $z$ 值为 $f(i,j,k)$。现在阿绫想知道，对于所有满足 $i<j<k$ 的 $(i,j,k)$，$f(i,j,k)$ 之和是多少呢？你只需要回答她这一答案对 $2^{32}$ 取模的结果。

输入格式

第一行一个整数 $n$ 表示音符序列的长度。

第二行三个整数 $a$，$b$，$c$。

第三行 $n$ 个整数表示 $s$ 序列，也就是每个音符的音高。

输出格式

一行一个整数即答案。

4
3 4 5
2 4 3 1

39

提示

样例解释

$f(1,2,3)=4$，其中一组最优的 $(s_i',s_j',s_k')$ 为 $(2,3,3)$。

$f(1,2,4)=13$，其中一组最优的 $(s_i',s_j',s_k')$ 为 $(2,2,2)$。

$f(1,3,4)=9$，其中一组最优的 $(s_i',s_j',s_k')$ 为 $(2,2,2)$。

$f(2,3,4)=13$，其中一组最优的 $(s_i',s_j',s_k')$ 为 $(3,3,3)$。

$f(i,j,k)$ 的总和为 $4+13+9+13=39$。

数据规模与约定

本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。

对于 $100\%$ 的数据，$3\le n\le5\times10^5$，$1\le s_i,a,b,c\le 10^9$。

对于不同的子任务，作如下约定：

子任务编号	$n$	特殊性质	子任务分值
$1$	$=3$	无	$5$
$2$	$\le300$
$3$	$\le1000$		$10$
$4$	$\le5\times10^3$		$20$
$5$	$\le5\times10^4$
$6$	$\le5\times10^5$	有
$7$		无

特殊性质：出现的不同音高不超过 $10$ 种。