{"problem":{"name":"「QFOI R2」钟声远带斜阳","description":{"content":"**注意：本题中的所有数列下标从 $0$ 开始。** 小 R 是一个可爱的女孩子，她喜欢研究无穷数列。 她称一个无穷数列 $b$ 是美妙的，当且仅当存在自然数 $k_0$，使得对于所有 $k\\ge k_0$，都满足 $b$ 中下标在区间 $[k_0,k]$ 内的所有数的和非负（即 $\\sum_{i=k_0}^kb_i\\ge 0$）。例如，数列 $\\alpha_i=i-5$ 是美妙的，取 $k_","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10412"},"statements":[{"statement_type":"Markdown","content":"**注意：本题中的所有数列下标从 $0$ 开始。**\n\n小 R 是一个可爱的女孩子，她喜欢研究无穷数列。\n\n她称一个无穷数列 $b$ 是美妙的，当且仅当存在自然数 $k_0$，使得对于所有 $k\\ge k_0$，都满足 $b$ 中下标在区间 $[k_0,k]$ 内的所有数的和非负（即 $\\sum_{i=k_0}^kb_i\\ge 0$）。例如，数列 $\\alpha_i=i-5$ 是美妙的，取 $k_0=5$ 符合要求；但 $\\beta_i=-i$ 不是美妙的。\n\n她目前只有一个长度为 $n$ 的有穷数列 $a$，可以进行任意次以下三种操作：\n\n1. 花费 $p$ 的代价，选择一个整数 $i$（$0\\le i < n$），将 $a_i$ 增加一。\n1. 花费 $q$ 的代价，选择一个整数 $i$（$0\\le i < n$），将 $a_i$ 删除，同时更新 $n$ 为新的数列长度。**不能将数列删空。**\n1. 花费 $r$ 的代价，选择两个整数 $i,j$（$0\\le i < j < n$），交换 $a_i$ 与 $a_j$。\n\n她希望在若干次操作后，用无限个有穷数列 $a$ 依次相接得到无穷数列 $b$（即 $b_i=a_{i\\bmod n}$），使得 $b$ 是美妙的。请你求出最小的代价。\n\n## Input\n\n第一行四个整数 $n,p,q,r$。\n\n第二行 $n$ 个整数，表示数列 $a$。\n\n## Output\n\n一行，一个整数，表示最小代价。\n\n[samples]\n\n## Note\n\n**样例 $1$ 解释**\n\n花费 $p=1$ 的代价将 $a_3$ 增加一，得到数列 $b=[2,-2,3,-2,-1,2,-2,3,-2,-1,\\cdots]$ 是美妙的，取 $k_0=2$ 符合要求。\n\n可以证明不存在代价更小的方案。\n\n---\n\n**样例 $2$ 解释**\n\n花费 $q=1$ 的代价将 $a_1$ 删除，得到数列 $b=[2,3,-3,-1,2,3,-3,-1,\\cdots]$ 是美妙的，取 $k_0=0$ 符合要求。\n\n可以证明不存在代价更小的方案。\n\n---\n\n**数据范围**\n\n**本题采用捆绑测试。只有通过子任务中所有测试点以及所有依赖的子任务，才能获得相应的分数。**\n\n对于全部数据：$1\\le n\\le 10^5$，$1\\le p,q,r\\le 10^9$，$|a_i|\\le 10^9$。\n\n- 子任务一（$10$ 分）：$n=1$。\n- 子任务二（$10$ 分）：$n\\le 10$。依赖子任务一。\n- 子任务三（$20$ 分）：$|a_i|\\le 1$。\n- 子任务四（$20$ 分）：$\\sum|a_i|\\le 10^5$。依赖子任务三。\n- 子任务五（$40$ 分）：无特殊限制。依赖子任务一、二、三、四。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10412","tags":["贪心","洛谷原创","O2优化","前缀和","差分","洛谷月赛"],"sample_group":[["5 1 2 5\n2 -2 3 -3 -1","1"],["5 2 1 5\n2 -2 3 -3 -1","1"],["5 1 1 1\n0 1 2 3 4","0"]],"created_at":"2026-03-03 11:09:25"}}