左右操作

题目描述

给定长度为 $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$ 的元素总和的最小可能值。

输入格式

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

输出格式

输出答案。

样例

5 4 3
5 5 0 6 3

14

选择 $x=2,y=2$ 进行操作后,数列 $A = (4,4,0,3,3)$,元素总和为 $14$。

这是能达到的最小值。

4 10 10
1 2 3 4

10

选择 $x=0,y=0$ 进行操作后,数列 $A = (1,2,3,4)$,元素总和为 $10$。

这是能达到的最小值。

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

-58

$L,R,A_i$ 可能为负数。

数据范围

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