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

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.

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.

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.

3 1 44 2 3output
1input
5 3 25 17 13 5 6output
8input
8 3 43 7 5 4 3 12 9 4output
13Note
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.
題意：
給你n個(gè)數(shù)，可以執(zhí)行兩種操作最多各一次，一是移除一個(gè)連續(xù)的序列，代價(jià)是序列長(zhǎng)度*a，二是選一些數(shù)改變1，即可以有的加一，有的減一，代價(jià)是數(shù)字個(gè)數(shù)*b，注意不可以將整個(gè)序列移走。
最終使得剩下所有數(shù)字的最大公約數(shù)大于1，求最少代價(jià)。
題解：
由于最后序列必不為空，那么a[1],a[n]至少留一個(gè)，那么可以將a[1]-1、a[1]、a[1]+1、a[n]-1、a[n]、a[n]+1六個(gè)數(shù)的所有質(zhì)因數(shù)預(yù)處理，然后枚舉每個(gè)質(zhì)因數(shù)為約數(shù)時(shí)的最小代價(jià)。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const ll inf=9e18;const ll mod=1000000007;const int maxn=1e6+100;VI V;int n;ll x,y;ll d[maxn][3],cost[maxn];int a[maxn];void solve(int x){    int i=2;    while(x!=1&&i*i<=x)    {        if(x%i==0)        {            V.pb(i);            while(x%i==0&&x!=1)                x/=i;        }        i++;    }    if(x>1) V.pb(x);}int main(){    scanf("%d%I64d%I64d",&n,&x,&y);    rep(i,1,n+1) scanf("%d",&a[i]);    rep(i,-1,2) solve(a[1]+i),solve(a[n]+i);    sort(V.begin(),V.end());    V.erase(unique(V.begin(),V.end()),V.end());    ll ans=inf;    rep(i,0,V.size())    {        int p=V[i];        memset(cost,0,sizeof(cost));        rep(i,1,n+1) rep(j,0,3) d[i][j]=inf;        rep(i,1,n+1)        {            if(a[i]%p==0) cost[i]=0;            else if((a[i]-1)%p==0||(a[i]+1)%p==0) cost[i]=1;            else cost[i]=-1;        }        rep(i,1,n+1)        {            if(cost[i]==0)            {                d[i][1]=min(d[i-1][0],d[i-1][1])+x;                d[i][0]=d[i-1][0];                d[i][2]=min(min(d[i-1][1],d[i-1][0])+x,d[i-1][2]);            }            else if(cost[i]==1)            {                d[i][1]=min(d[i-1][0],d[i-1][1])+x;                d[i][0]=d[i-1][0]+y;                d[i][2]=min(min(d[i-1][1],d[i-1][0])+x,d[i-1][2]+y);            }            else            {                d[i][0]=inf;                d[i][1]=min(d[i-1][1],d[i-1][0])+x;                d[i][2]=min(min(d[i-1][1],d[i-1][0])+x,inf);            }        }        ll res=inf;        rep(i,0,3) res=min(res,d[n][i]);        ans=min(ans,res);    }    printf("%I64d/n",ans);    return 0;}