[R19D]构造序列 - 代码源竞赛平台

时空限制

1S/512M

题目描述

apiadu 有一个初始为空的序列，他需要通过两种神奇的操作来构造出目标序列 $c$：

• 批量添加：选定任意非负整数 $k,x$，可以一次性在序列末尾添加 $k$ 个相同的数字 $x$，执行这个操作的所需金币为 $A$。

• 连续添加：选定任意非负整数 $k,x$，可以一次性在序列末尾添加 $k$ 个从 $x$ 开始的连续的数字，（即 $x$, $x+1$, $\cdots$, $x+k-1$）。 执行这个操作的所需金币为 $B$。

请你帮助 apiadu 计算出，构造出给定的目标序列所需的最少金币数量。

格式

输入格式

第一行包含三个整数 $n,A,B$，分别表示目标序列的长度，操作 $1$ 的金币数，操作 $2$ 的金币数。

第二行包含 $n$ 个整数 $c_i$，表示目标序列。

输出格式

输出一个整数，表示构造目标序列所需的最少金币数量。

样例

样例输入 #1

5 3 2 
1 1 2 3 4

样例输出 #1

4

样例解释 #1

• 第一次操作：使用操作 $2$（其中 $k = 1,x = 1$），添加 $1$ 个 $1$，此时序列为 [$\color{red} {1}$] ，花费 $2$ 个金币。

• 第二次操作：使用操作 $2$ （其中 $k = 4,x = 1$），此时序列为 [$\color{red}{1}$ $,$ $\color{blue} {1}$ $,$ $\color{blue}{2}$ $,$ $\color{blue} {3}$ $,$ $\color{blue} {4}$] ，花费 $2$ 个金币。

总的花费数量为 $2 + 2 = 4$ 个金币。

数据规模

对于 $50\%$ 的数据，$1 \leq n \leq 1000$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$， $1 \leq A, B ,c_i \leq 10^9$。