背景

译自 Northwestern Europe Regional Contest (NWERC) 2019。

题目描述

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$)，表示每条评论当前的分数。

输出格式

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

4 10 50
8 8 2 -2

80

6 100 33
5 -13 0 0 -12 0

132

提示

【数据规模与约定】

• $1\le n\le 5\cdot 10^5$。
• $1\le c,r\le 10^9$。
• $-10^9\le s_i\le 10^9$。
• 答案输出为一个整数。