/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 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 は負であることがあります。
Score : 400 points
Problem Statement
You are given an integer sequence of length N: A=(A_1,A_2,\ldots,A_N).
You will perform the following consecutive operations just once:
-
Choose an integer x (0\leq x \leq N). If x is 0, do nothing. If x is 1 or greater, replace each of A_1,A_2,\ldots,A_x with L.
-
Choose an integer y (0\leq y \leq N). If y is 0, do nothing. If y is 1 or greater, replace each of A_{N},A_{N-1},\ldots,A_{N-y+1} with R.
Print the minimum possible sum of the elements of A after the operations.
Constraints
- 1 \leq N \leq 2\times 10^5
- -10^9 \leq L, R\leq 10^9
- -10^9 \leq A_i\leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L R A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
5 4 3 5 5 0 6 3
Sample Output 1
14
If you choose x=2 and y=2, you will get A = (4,4,0,3,3), for the sum of 14, which is the minimum sum achievable.
Sample Input 2
4 10 10 1 2 3 4
Sample Output 2
10
If you choose x=0 and y=0, you will get A = (1,2,3,4), for the sum of 10, which is the minimum sum achievable.
Sample Input 3
10 -5 -3 9 -6 10 -1 2 10 -1 7 -15 5
Sample Output 3
-58
L, R, and A_i may be negative.