You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

区间修改

题目描述

给你一行 $n$ 个元素的序列 $a_i$ 和两个整数 $l, r$, 你可以对该序列进行如下操作 $1$ 次.

• 任选一个下标 $x (0 \le x \le n)$, 将 $a_1, a_2, \dots a_x$ 的值修改为 $l$, 如果 $x$ 为 $0$, 则什么都没有改变
• 任选一个下标 $x (0 \le x \le n)$, 将 $a_x, a_{x+1}, \dots a_n$ 的值修改为 $r$, 如果 $x$ 为 $0$, 则什么都没有改变

现在我们想知道, 最终 $a$ 序列和的最小值是多少?

输入格式

第一行三个整数 $n, l, r$

第二行输入一行 $n$ 个元素表示序列 $a$

输出格式

输出一个整数表示修改后序列和的最小值

样例 #1

样例输入 #1

5 4 3
5 5 0 6 3

样例输出 #1

14

样例 #2

样例输入 #2

4 10 10
1 2 3 4

样例输出 #2

10

样例 #3

样例输入 #3

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

样例输出 #3

-58

提示

• $1\le n\le 2 \times 10^5$
• $-10^9 \le l, r \le 10^9$
• $-10^9 \le a_i \le 10^9$