当前没有测试数据。

D - 左右操作

得分: $400$ 分

题目描述

给定一个长度为 $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$

输出

输出答案。

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$ 可能为负数。