题目描述

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

你需要恰好进行一次如下连续操作：

• 选择一个整数 $x\ (0\leq x \leq N)$。如果选择 $x=0$，则什么都不做。如果选择 $x\geq 1$，则将 $A_1,A_2,\ldots,A_x$ 分别替换为 $L$。
• 选择一个整数 $y\ (0\leq y \leq N)$。如果选择 $y=0$，则什么都不做。如果选择 $y\geq 1$，则将 $A_N,A_{N-1},\ldots,A_{N-y+1}$ 分别替换为 $R$。

请你求出经过操作后，序列 $A$ 的所有元素之和可能取得的最小值。

输入格式

输入以如下格式从标准输入给出。

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

输出格式

请输出答案。

样例 1

输入

5 4 3
5 5 0 6 3

输出

14

样例 2

输入

4 10 10
1 2 3 4

输出

10

样例 3

输入

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

输出

-58

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $-10^9\leq L,R\leq 10^9$
• $-10^9\leq A_i\leq 10^9$
• 输入均为整数

样例解释 1

当 $x=2, y=2$ 时，数列 $A=(4,4,0,3,3)$，元素之和为 $14$，这是可以达到的最小值。

样例解释 2

当 $x=0, y=0$ 时，数列 $A=(1,2,3,4)$，元素之和为 $10$，这是可以达到的最小值。

样例解释 3

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

由 ChatGPT 4.1 翻译