Вам надано послідовність цілих чисел довжини \(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\).

Вивести мінімально можливу суму елементів \(А\) після операцій.

Обмеження

• \(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\)

Наступний  рядок містить \(N\) цілих чисел \(A_i\)

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть відповідь.

Примітка

До прикладу 1:

Якщо вибрати x=2 і y=2, ви отримаєте A = (4,4,0,3,3), на суму 14, що є мінімально сумою.

Приклад вхідних даних

5 4 3
5 5 0 6 3

Приклад вихідних даних

14

Приклад вхідних даних

4 10 10
1 2 3 4

Приклад вихідних даних

10

Приклад вхідних даних

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

Приклад вихідних даних

-58