You are given array ai of length n. You may consecutively apply two operations to this array:

  * remove some subsegment (continuous subsequence) of length m < n and pay for it m·a coins; 
  * change some elements of the array by at most 1, and pay b coins for each change. 



Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.

Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.

Input

The first line of the input contains integers n, a and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — 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 (2 ≤ ai ≤ 109) — elements of the array.

Output

Print a single number — the minimum cost of changes needed to obtain an array, such that the greatest common divisor of all its elements is greater than 1.

Examples

Input

3 1 4
4 2 3


Output

1


Input

5 3 2
5 17 13 5 6


Output

8


Input

8 3 4
3 7 5 4 3 12 9 4


Output

13

Note

In the first sample the optimal way is to remove number 3 and pay 1 coin for it.

In the second sample you need to remove a segment [17, 13] and then decrease number 6. The cost of these changes is equal to 2·3 + 2 = 8 coins.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author AlexFetisov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB_AIM_1 solver = new TaskB_AIM_1();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB_AIM_1 {
        private static final long INF = Long.MAX_VALUE / 4;
        int B;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int A = in.nextInt();
            B = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = in.nextInt();
            }
            if (n == 1) {
                out.println(0);
                return;
            }
            long res = solve(a, A);
            ArrayUtils.reverse(a);
            res = Math.min(res, solve(a, A));
            out.println(res);
        }

        private long solve(int[] a, int A) {
            long res = INF;
            TreeSet<Long> set = new TreeSet<Long>();
            List<Pair<Long, Integer>> p = IntegerUtils.factorize(a[0]);
            for (Pair<Long, Integer> pp : p) {
                set.add(pp.first);
            }
            p = IntegerUtils.factorize(a[0] - 1);
            for (Pair<Long, Integer> pp : p) {
                set.add(pp.first);
            }
            p = IntegerUtils.factorize(a[0] + 1);
            for (Pair<Long, Integer> pp : p) {
                set.add(pp.first);
            }
            for (long x : set) {
                if (x != 1) {
                    res = Math.min(res, solve(a, A, (int) x));
                }
            }
            return res;
        }

        private long solve(int[] a, int A, int X) {
            long d0 = getCost(a[0], X), d1 = INF, d2 = INF;
            for (int i = 1; i < a.length; ++i) {
                long xx = getCost(a[i], X);
                // we didn't start interval
                long nd0 = d0 + xx;
                // we start new interval or continue interval now
                long nd1 = d0 + A;
                if (d1 < INF) {
                    nd1 = Math.min(nd1, d1 + A);
                }
                // we stop interval or continue now
                long nd2 = INF;
                if (d1 < INF) {
                    nd2 = d1 + xx;
                }
                if (d2 < INF) {
                    nd2 = Math.min(nd2, d2 + xx);
                }
                d0 = nd0;
                d1 = nd1;
                d2 = nd2;
                if (d0 > INF) {
                    d0 = INF;
                }
                if (d1 > INF) {
                    d1 = INF;
                }
                if (d2 > INF) {
                    d2 = INF;
                }
            }

            return Math.min(d0, Math.min(d1, d2));
        }

        private long getCost(long a, long x) {
            if (a % x == 0) return 0;
            if ((a + 1) % x == 0) return B;
            if ((a - 1) % x == 0) return B;
            return INF;
//        long full = a / x;
//        long delta = a - full * 1L * x;
//        long delta2 = (full + 1) * 1L * x - a;
//        return Math.min(delta, delta2);
        }

    }

    static class Pair<U, V> implements Comparable<Pair<U, V>> {
        public final U first;
        public final V second;

        public static <U, V> Pair<U, V> makePair(U first, V second) {
            return new Pair<U, V>(first, second);
        }

        public Pair(U first, V second) {
            this.first = first;
            this.second = second;
        }


        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair pair = (Pair) o;

            return !(first != null ? !first.equals(pair.first) : pair.first != null) && !(second != null ? !second.equals(pair.second) : pair.second != null);

        }


        public int hashCode() {
            int result = first != null ? first.hashCode() : 0;
            result = 31 * result + (second != null ? second.hashCode() : 0);
            return result;
        }


        public String toString() {
            return "(" + first + "," + second + ")";
        }

        @SuppressWarnings({"unchecked"})
        public int compareTo(Pair<U, V> o) {
            int value = ((Comparable<U>) first).compareTo(o.first);
            if (value != 0)
                return value;
            return ((Comparable<V>) second).compareTo(o.second);
        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer stt;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public String nextString() {
            while (stt == null || !stt.hasMoreTokens()) {
                stt = new StringTokenizer(nextLine());
            }
            return stt.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }

    static class ArrayUtils {
        public static void reverse(int[] order) {
            for (int i = 0, j = order.length - 1; i < j; ++i, --j) {
                int t = order[i];
                order[i] = order[j];
                order[j] = t;
            }
        }

    }

    static class IntegerUtils {
        public static List<Pair<Long, Integer>> factorize(long number) {
            List<Pair<Long, Integer>> result = new ArrayList<Pair<Long, Integer>>();
            for (long i = 2; i * i <= number; i++) {
                if (number % i == 0) {
                    int power = 0;
                    do {
                        power++;
                        number /= i;
                    } while (number % i == 0);
                    result.add(Pair.makePair(i, power));
                }
            }
            if (number != 1) {
                result.add(Pair.makePair(number, 1));
            }
            return result;
        }

    }
}

