623_B. Array GCD_28664
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 javafx.util.Pair;

import java.io.*;
import java.lang.reflect.Array;
import java.lang.reflect.Parameter;
import java.util.*;

public class Main {


    private static final long INF = Long.MAX_VALUE >> 2;

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader reader = new InputReader(inputStream);
        PrintWriter writer = new PrintWriter(outputStream);
        new Main().main(reader, writer);
        writer.close();
    }

    int[] a;
    long[] order;
    long[] reverse;
    int n;
    long removeCost, changeCost;

    void main(InputReader reader, PrintWriter writer) {
        n = reader.nextInt();
        removeCost = reader.nextInt();
        changeCost = reader.nextInt();
        a = new int[n + 2];
        order = new long[n + 2];
        reverse = new long[n + 2];
        for (int i = 1; i <= n; ++i) {
            a[i] = reader.nextInt();
        }
        ArrayList<Integer> divisors = new ArrayList<>();
        HashSet<Integer> hashSet = new HashSet<>();
        hashSet.addAll(getPrimeDivisor(a[1]));
        hashSet.addAll(getPrimeDivisor(a[1] + 1));
        hashSet.addAll(getPrimeDivisor(a[1] - 1));
        hashSet.addAll(getPrimeDivisor(a[n]));
        hashSet.addAll(getPrimeDivisor(a[n] + 1));
        hashSet.addAll(getPrimeDivisor(a[1]));
        long ans = INF;
        int[] queue = new int[n + 2];
        for (Integer divisor : hashSet) {
//            writer.println("divisor " + divisor);
            firstUsed(n, divisor);
            lastUsed(n, divisor);
//            for (int i = 1; i <= n; ++i) {
//                writer.println(order[i] + " " + reverse[i]);
//            }
            int front = 0, rear = 0;
            for (int j = n; j >= 1; --j) {
                while (front < rear) {
                    int last = queue[rear - 1];
                    if (reverse[last] >= reverse[j]) {
                        --rear;
                    } else {
                        break;
                    }
                }
                queue[rear++] = j;
            }

            if (front < rear) {
                ans = Math.min(ans, reverse[queue[front]]);
            }
            for (int i = 1; i <= n; ++i) {
                while (front < rear && i + queue[front] > n) {
                    ++front;
                }
                long tmp = order[i];
                if (front < rear) {
                    tmp += reverse[queue[front]];
                }
                ans = Math.min(ans, tmp);
                ans = Math.min(ans, order[i]);
            }
        }
        ans += n * removeCost;
        writer.println(ans);
    }

    void firstUsed(int n, int divisor) {
        Arrays.fill(order, 1, n + 1, INF);
        for (int i = 1; i <= n; ++i) {
            order[i] = order[i - 1] - removeCost;
            int k = a[i];
            if (k % divisor == 0) {
            } else if ((k + 1) % divisor == 0) {
                order[i] += changeCost;
            } else if ((k - 1) % divisor == 0) {
                order[i] += changeCost;
            } else {
                order[i] = INF;
                return;
            }
        }
    }

    void lastUsed(int n, int divisor) {
        Arrays.fill(reverse, 1, n + 1, INF);
        for (int i = 1; i <= n; ++i) {
            reverse[i] = reverse[i - 1] - removeCost;
            int k = a[n - i + 1];
            if (k % divisor == 0) {
            } else if ((k + 1) % divisor == 0) {
                reverse[i] += changeCost;
            } else if ((k - 1) % divisor == 0) {
                reverse[i] += changeCost;
            } else {
                reverse[i] = INF;
                return;
            }
        }

    }

    ArrayList<Integer> getPrimeDivisor(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                list.add(i);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1) {
            list.add(n);
        }
        return list;
    }

}


class InputReader {
    StringTokenizer tokenizer;
    BufferedReader reader;

    InputReader(InputStream inputStream) {
        tokenizer = null;
        reader = new BufferedReader(new InputStreamReader(inputStream));
    }

    String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return tokenizer.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }
}
5 3 2
5 17 13 5 6
 3 1 4
4 2 3
 8 3 4
3 7 5 4 3 12 9 4
 5 3 2
5 11 13 5 6
 5 2 10
124 777 617 616 618
 100 533 837
6 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6
 6 4 10
577 576 883 679 883 864
 5 3 5
7 4 7 4 8
 3 3 0
463 926 925
 5 10 1
1300333 1300332 2600666 1300334 1300332
 2 7 5
5 7
 10 8 4
803 402 803 803 801 226 802 801 401 801
 1 334159859 249565919
52
 1 155 276
104
 93 1985 9702
1711 6269 9689 9119 569 3990 5129 6314 2171 4078 2607 3063 5410 7140 7831 4622 2597 8486 9050 3110 1673 5435 8981 6871 4679 8854 5675 39 7227 2533 1782 7833 7029 5919 7792 4192 5856 6020 4735 9772 3145 8757 3853 6371 7217 815 6643 837 3490 1667 2360 983 653 2708 5795 9203 1405 2875 7590 2682 8667 5369 8371 1235 3093 1802 483 2359 677 2044 4556 8403 6419 301 7410 1964 9587 392 1712 1105 7882 3215 5212 1885 1772 4865 1248 7410 9690 6840 7981 8550 4561
 45 393296667 817784089
513035443 513035443 513035445 513035445 513035443 555648978 463549879 830693049 524420119 541365334 562791911 736173182 644390537 639730339 913702156 807631127 679411095 457747249 554394051 803981524 901463184 651788488 792766018 587562656 564169971 645381787 497940709 886010956 577261234 513035444 513035443 513035443 513035445 513035445 513035444 513035444 513035443 513035443 513035445 513035445 513035443 513035443 513035443 513035443 513035445
 6 100 1
3 2 2 2 2 3
 7 735937743 207711841
806 400 667 521 729 413 878
 1 5 7
99
 6 128454855 323141531
920 204 261 770 485 919
 13 219 292
796 798 798 797 328 263 148 931 92 578 262 798 796
 7 46 23
47 17 90 30 39 6 63
 2 5 7
2 5
 3 63 569
764 383 381
 1 6 2
9
 2 965 473
569 780
 4 457 423
559 559 561 559
 5 1 1
1300333 1300332 2600666 1300334 1300332
 3 4 3
9 9 4
 2 10 2
11 13
 1 476059451 940757790
609
 5 3 2
5 11 13 5 9
 5 2 10
124 777 617 310 618
 100 533 837
6 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 9 5 5 5 5 5 5 6
 6 4 10
577 576 883 679 1014 864
 5 3 0
7 4 7 4 8
 3 3 1
463 926 925
 2 2 5
5 7
 93 1985 9702
1711 6269 9689 9119 569 3990 5129 6314 2171 4078 2607 3063 5410 7140 7831 4622 2597 8486 9050 3110 1673 5435 8981 6871 4679 8854 5675 39 7227 2533 1782 7833 7029 5919 7792 4192 5856 6020 4735 9772 3145 8757 3853 6371 7217 815 6643 837 3490 1667 2360 983 653 2708 5795 9203 1405 2875 7590 2682 8667 5369 8371 1714 3093 1802 483 2359 677 2044 4556 8403 6419 301 7410 1964 9587 392 1712 1105 7882 3215 5212 1885 1772 4865 1248 7410 9690 6840 7981 8550 4561
 45 393296667 817784089
513035443 513035443 513035445 513035445 513035443 555648978 463549879 830693049 524420119 541365334 562791911 736173182 644390537 639730339 913702156 1004981832 679411095 457747249 554394051 803981524 901463184 651788488 792766018 587562656 564169971 645381787 497940709 886010956 577261234 513035444 513035443 513035443 513035445 513035445 513035444 513035444 513035443 513035443 513035445 513035445 513035443 513035443 513035443 513035443 513035445
 7 735937743 207711841
806 400 576 521 729 413 878
 6 128454855 323141531
920 273 261 770 485 919
 13 219 124
796 798 798 797 328 263 148 931 92 578 262 798 796
 7 46 23
73 17 90 30 39 6 63
 3 63 569
764 383 373
 2 965 473
569 585
 4 457 423
14 559 561 559
 3 4 3
9 9 2
 5 3 2
9 17 13 5 6
 8 3 4
3 7 5 4 3 12 0 4
 100 533 837
6 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 9 5 5 5 5 5 5 5 5 5 5 9 5 5 5 5 5 5 6
 7 46 23
73 17 90 30 31 6 63
 3 63 569
764 108 373
 4 457 423
20 559 561 559
 8 3 4
3 7 5 6 3 12 0 4
 100 533 837
6 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 8 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 9 5 5 5 5 5 5 5 5 5 5 9 5 5 5 5 5 5 6
 6 7 10
577 576 883 679 1014 651
 5 11 1
1300333 1300332 2600666 1300334 1300332
 1 155 300
104
 6 100 1
3 2 0 2 2 3
 1 5 7
23
 2 5 0
2 5
 5 1 1
1300333 1300332 2600666 1300334 394714
 2 10 2
8 13
 1 476059451 940757790
150
 3 1 0
4 2 3
 5 2 10
225 777 617 310 618
 6 4 10
577 576 883 679 1014 651
 5 3 0
7 4 7 4 3
 3 0 1
463 926 925
 5 14 1
1300333 1300332 2600666 1300334 1300332
 2 1 5
5 7
 1 31 300
104
 93 1985 9702
1711 6269 9689 9119 569 3990 5129 6314 2171 4078 2607 3063 5410 7140 7831 4622 2597 8486 9050 3110 1673 5435 8981 6871 4679 8854 5675 39 7227 2533 1782 7833 7029 5919 7792 4192 5856 6020 4735 9772 3145 8757 3853 6371 7217 815 6643 837 3490 1667 2360 983 653 2708 5795 9203 1405 2875 7590 2938 8667 5369 8371 1714 3093 1802 483 2359 677 2044 4556 8403 6419 301 7410 1964 9587 392 1712 1105 7882 3215 5212 1885 1772 4865 1248 7410 9690 6840 7981 8550 4561
 45 393296667 817784089
513035443 513035443 513035445 513035445 513035443 555648978 463549879 830693049 524420119 541365334 562791911 736173182 644390537 639730339 913702156 1004981832 679411095 457747249 554394051 803981524 901463184 651788488 792766018 587562656 564169971 645381787 497940709 886010956 577261234 513035444 513035443 513035443 513035445 513035445 513035444 513035444 513035443 125371441 513035445 513035445 513035443 513035443 513035443 513035443 513035445
 7 735937743 207711841
806 400 458 521 729 413 878
 6 128454855 323141531
920 81 261 770 485 919
 13 219 124
12 798 798 797 328 263 148 931 92 578 262 798 796
 2 5 0
2 10
 2 965 473
740 585
 5 1 1
1300333 1300332 2950479 1300334 394714
 3 2 3
9 9 2
 2 10 2
8 2
 1 476059451 84557068
150
 4 2 10
225 777 617 310 618
 5 3 0
11 4 7 4 3
 5 14 2
1300333 1300332 2600666 1300334 1300332
 1 1 5
5 7
 1 31 449
104
 93 1985 9702
1711 6269 9689 9119 569 3990 5129 6314 2171 4078 2607 3063 5410 7140 7831 4622 2597 8486 9050 3110 1673 5435 8981 6871 4679 8854 5675 39 7227 2533 1782 4730 7029 5919 7792 4192 5856 6020 4735 9772 3145 8757 3853 6371 7217 815 6643 837 3490 1667 2360 983 653 2708 5795 9203 1405 2875 7590 2938 8667 5369 8371 1714 3093 1802 483 2359 677 2044 4556 8403 6419 301 7410 1964 9587 392 1712 1105 7882 3215 5212 1885 1772 4865 1248 7410 9690 6840 7981 8550 4561
 45 393296667 817784089
513035443 513035443 513035445 513035445 513035443 1110463421 463549879 830693049 524420119 541365334 562791911 736173182 644390537 639730339 913702156 1004981832 679411095 457747249 554394051 803981524 901463184 651788488 792766018 587562656 564169971 645381787 497940709 886010956 577261234 513035444 513035443 513035443 513035445 513035445 513035444 513035444 513035443 125371441 513035445 513035445 513035443 513035443 513035443 513035443 513035445

                                                               8
                                                                1
                                                               13
                                                                7
                                                                4
                                                             1370
                                                               20
                                                                8
                                                                0
                                                                1
                                                                7
                                                               24
                                                                0
                                                                0
                                                           182620
 16911756681
                                                                2
                                                        830847364
                                                                0
                                                        513819420
                                                              803
                                                               46
                                                                5
                                                              126
                                                                0
                                                              473
                                                              457
                                                                1
                                                                3
                                                                4
                                                                0
 7
 4
 2207
 16
 0
 1
 2
 182620
 16911756681
 623135523
 580051241
 372
 46
 126
 473
 880
 3
 6
 13
 3044
 69
 63
 1269
 10
 3881
 24
 1
 0
 2
 0
 0
 1
 2
 0
 0
 4
 16
 0
 0
 1
 1
 0
 182620
 16911756681
 623135523
 580051241
 372
 0
 0
 2
 2
 0
 0
 4
 0
 2
 0
 0
 182620
 16911756681
