Problem Description

Note: In this problem, all sequence indices start from $0$.

Little R is a lovely girl who likes studying infinite sequences.

She calls an infinite sequence $b$ wonderful if and only if there exists a natural number $k_0$ such that for all $k \ge k_0$, the sum of all numbers in $b$ with indices in the interval $[k_0, k]$ is non-negative (that is, $\sum_{i=k_0}^k b_i \ge 0$). For example, the sequence $\alpha_i = i - 5$ is wonderful, taking $k_0 = 5$ works; but $\beta_i = -i$ is not wonderful.

She currently only has a finite sequence $a$ of length $n$, and she can perform the following three operations any number of times:

1. Pay cost $p$, choose an integer $i$ ($0 \le i < n$), and increase $a_i$ by $1$.
2. Pay cost $q$, choose an integer $i$ ($0 \le i < n$), delete $a_i$, and update $n$ to be the new length of the sequence. You cannot delete the sequence until it becomes empty.
3. Pay cost $r$, choose two integers $i, j$ ($0 \le i < j < n$), and swap $a_i$ and $a_j$.

She hopes that after some operations, by concatenating infinitely many copies of the finite sequence $a$ in order, she obtains an infinite sequence $b$ (i.e., $b_i = a_{i \bmod n}$), such that $b$ is wonderful. Please find the minimum total cost.

Input Format

The first line contains four integers $n, p, q, r$.

The second line contains $n$ integers, representing the sequence $a$.

Output Format

One line with one integer, representing the minimum cost.

5 1 2 5
2 -2 3 -3 -1

1

5 2 1 5
2 -2 3 -3 -1

1

5 1 1 1
0 1 2 3 4

0

Hint

Explanation of Sample $1$

Pay cost $p = 1$ to increase $a_3$ by $1$, obtaining the sequence $b = [2, -2, 3, -2, -1, 2, -2, 3, -2, -1, \cdots]$, which is wonderful. Taking $k_0 = 2$ satisfies the requirement.

It can be proven that no solution with a smaller cost exists.

Explanation of Sample $2$

Pay cost $q = 1$ to delete $a_1$, obtaining the sequence $b = [2, 3, -3, -1, 2, 3, -3, -1, \cdots]$, which is wonderful. Taking $k_0 = 0$ satisfies the requirement.

It can be proven that no solution with a smaller cost exists.

Constraints

This problem uses bundled testdata. Only by passing all test points of a subtask and all the subtasks it depends on can you get the corresponding score.

For all testdata: $1 \le n \le 10^5$, $1 \le p, q, r \le 10^9$, $|a_i| \le 10^9$.

• Subtask 1 ($10$ points): $n = 1$.
• Subtask 2 ($10$ points): $n \le 10$. Depends on Subtask 1.
• Subtask 3 ($20$ points): $|a_i| \le 1$.
• Subtask 4 ($20$ points): $\sum |a_i| \le 10^5$. Depends on Subtask 3.
• Subtask 5 ($40$ points): No special restrictions. Depends on Subtasks 1, 2, 3, and 4.

Translated by ChatGPT 5