612. Array GCD
0
Medium
Given an array ai of length n, you have the option to perform two operations consecutively:
1. Remove a subsegment (a continuous subsequence) of length m < n and pay m·a coins for it.
2. Change some elements of the array by at most 1, paying b coins for each change.
Note that each operation can be applied at most once (or not at all), and you can only remove one segment. Additionally, each number in the array can be changed (increased or decreased) by at most 1. Deleting the entire array is not allowed.
Your objective is to calculate the minimum number of coins required to ensure that the greatest common divisor of the resulting array's elements is greater than 1.
Input Format
The first line of the input consists of three integers: n, a, and b. These represent the length of the array, the cost of removing a single element in the first operation, and the cost of changing an element, respectively.
The second line contains n integers ai, which are the elements of the array.
The second line contains n integers ai, which are the elements of the array.
Output Format
Output a single number, which represents the minimum cost of changes required to obtain an array where the greatest common divisor of all its elements is greater than 1.
Example
Input
3 1 4
4 2 3
Output
1
Constraints
1 ≤ n ≤ 1000000
0 ≤ a, b ≤ 109
0 ≤ a, b ≤ 109
Loading...
View Submissions
Console