P10412 "QFOI R2" The Bell Tolls Far Under the Slanting Sun

**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$. 1. 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.** 1. 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.

The first line contains four integers $n, p, q, r$. The second line contains $n$ integers, representing the sequence $a$.

One line with one integer, representing the minimum cost.

**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