P17008 [NWERC 2019] 寒鸦与乌鸦 / Jackdaws And Crows

译自 [Northwestern Europe Regional Contest (NWERC) 2019](http://2019.nwerc.eu)。

Nick 是一名观鸟爱好者，经常访问论坛 CrowFinders，与志同道合的人讨论爱好。CrowFinders 有一个投票系统，用户可以给评论点赞或点踩，使评论得分分别增加或减少 $1$。因此每条评论最终可以得到任意整数分数，包括负数。 有一次，Nick 浏览一场关于寒鸦是否属于乌鸦的激烈讨论时，发现了一串令他非常满意的评论链：这串评论的分数在正负之间交替。但几天后，他发现这条评论链不再交替。现在 Nick 想让它重新交替。 如果一条评论链的分数 $s_1,s_2,\ldots,s_n$ 全部非零，并且任意相邻两个分数 $s_i,s_{i+1}$ 符号相反，则这条评论链是交替的。特别地，单条非零分数评论，甚至空评论链，也被视为交替评论链。 Nick 可以使用两种操作使评论链交替： 1. 创建一个小号，并用它给一些评论点赞或点踩。这会使相应评论得分增加或减少 $1$。每个小号对每条评论至多投一次票，但可以对任意子集的评论投票。创建并使用一个小号需要 $c$ 秒，与它投了多少条评论无关。 2. 举报某一条具体评论，将其从评论链中移除。想出令人信服的举报理由需要 $r$ 秒。（Nick 很擅长辩论，因此一旦提交举报，该评论一定会被移除。） Nick 可以按任意顺序、任意次数使用这些操作。他最快需要多长时间才能让评论链交替？ 例如，对于样例 $1$，评论分数为 $8,8,2,-2$，创建一个小号需要 $10$ 秒，举报一条评论需要 $50$ 秒。此时最优做法是先创建 $3$ 个小号，让它们给第四条评论点赞并给第三条评论点踩，然后举报第一条评论。结果分数变为 $8,-1,1$，成为交替评论链，总耗时 $80$ 秒。

输入包含： - 第一行包含三个整数 $n,c,r$ ($1\le n\le 5\cdot 10^5$, $1\le c,r\le 10^9$)，分别表示评论数量、创建一个小号所需时间、举报一条评论所需时间。 - 第二行包含 $n$ 个整数 $s_1,\ldots,s_n$ ($-10^9\le s_i\le 10^9$)，表示每条评论当前的分数。

输出一个整数，表示通过上述操作使评论链交替所需的最短时间。

【数据规模与约定】 - $1\le n\le 5\cdot 10^5$。 - $1\le c,r\le 10^9$。 - $-10^9\le s_i\le 10^9$。 - 答案输出为一个整数。