题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\\ldots,A_N)$。

你需要执行以下操作：

• 选择一个整数 $x$ $(0\\leq x \\leq N)$。如果 $x=0$，不执行任何操作。如果 $x$ 大于等于 $1$，则将 $A_1,A_2,\\ldots,A_x$ 中的每个元素替换为 $L$。

• 选择一个整数 $y$ $(0\\leq y \\leq N)$。如果 $y=0$，不执行任何操作。如果 $y$ 大于等于 $1$，则将 $A_{N},A_{N-1},\\ldots,A_{N-y+1}$ 中的每个元素替换为 $R$。

打印出进行操作后 $A$ 的元素和的最小可能值。

约束条件

• $1 \\leq N \\leq 2\\times 10^5$
• $\-10^9 \\leq L, R\\leq 10^9$
• $\-10^9 \\leq A_i\\leq 10^9$
• 输入中的所有值都是整数。

输入格式

输入以标准输入给出，格式如下：

$N$ $L$ $R$ $A_1$ $A_2$ $\\ldots$ $A_N$

输出格式

输出答案。

示例输入 1

5 4 3
5 5 0 6 3

示例输出 1

14

如果选择 $x=2$ 和 $y=2$，则得到 $A = (4,4,0,3,3)$，元素和为 $14$，这是最小可能值。

示例输入 2

4 10 10
1 2 3 4

示例输出 2

10

如果选择 $x=0$ 和 $y=0$，则得到 $A = (1,2,3,4)$，元素和为 $10$，这是最小可能值。

示例输入 3

10 -5 -3
9 -6 10 -1 2 10 -1 7 -15 5

示例输出 3

-58

$L$、$R$ 和 $A_i$ 可能为负数。