#2800. [Poi2012]Leveling Ground

内存限制:64 MiB 时间限制:10 Sec

题目描述

Description
给出n个整数X_1,X_2,...X_n,再给出两个正整数a、b,可以进行下面四种操作:
1. 选择正整数l,r (1<=l<=r<=n),将X_l,X_{l+1},...,X_r都加上a。
2. 选择正整数l,r (1<=l<=r<=n),将X_l,X_{l+1},...,X_r都减去a。
3. 选择正整数l,r (1<=l<=r<=n),将X_l,X_{l+1},...,X_r都加上b。
4. 选择正整数l,r (1<=l<=r<=n),将X_l,X_{l+1},...,X_r都减去b。
求最少的操作次数将{X_i}全部变成0

输入格式


第一行三个正整数n,a,b (n<=100,000, a,b<=10^9)。
第二行n个整数,依次表示X_1,X_2,...X_n (|X_i|<=10^9)。

输出格式

一个正整数,表示最少的操作次数。如果不存在方案,输出-1。

样例

样例输入


			
5 2 3
1 2 1 1 -1

样例输出


			
5

数据范围与提示

进行下面五次操作将{X_i}全部变成0:

1. 将X_1,X_2都加上2,变成3 4 1 1 -1。

2. 将X_1,X_2都减去3,变成0 1 1 1 -1。

3. 将X_2,X_3,X_4,X_5都加上2,变成0 3 3 3 1。

4. 将x_5加上2,变成0 3 3 3 3。

5. 将x_2,x_3,x_4,x_5都减去3,变成0 0 0 0 0。