题目描述

译自 POI 2012 Stage 3. Day 1「Leveling Ground」

给定一个长度为 $n$ 的数组，每次操作可以将一个连续区间的数增加或减少 $a$，或将一个连续区间的数增加或减少 $b$。
求使整个数组变为 $0$ 的最小操作次数。若无解请输出 $-1$。

输入格式

第一行三个整数 $n, a, b$（$1 \le n \le 100\,000$, $1 \le a,b \le 10^9$）。

接下来一行 $n$ 个整数 $h_1, h_2, \ldots, h_n$，绝对值均不超过 $10^9$。

输出格式

输出一行一个整数，表示最小操作次数。

样例

输入

5 2 3
1 2 1 1 -1

输出

5

一种操作方案是：

1. 将前两个数加 $2$；
2. 将前两个数减 $3$；
3. 将后四个数加 $2$；
4. 将最后一个数加 $2$；
5. 将后四个数减 $3$。

数据范围与提示

• 对于 $30\%$ 的数据，$n,a,b \le 200$，$-200 \le h_i \le 200$。
• 对于 $60\%$ 的数据，$n,a,b \le 2000$，$-2000 \le h_i \le 2000$。
• 对于 $90\%$ 的数据，$a,b \le 10^6$。
• 对于所有数据，$1 \le n \le 100\,000$，$1 \le a,b \le 10^9$。