1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const int N=200010;
int n,m,i,x,y,k,b[N],q[N],lim,pre[N],nxt[N],w[N];ll a[N],ans[N],cur,cnt;
priority_queue<P,vector<P>,greater<P> >Q;
inline bool cmp(int x,int y){return b[x]<b[y];}
inline ll ask(ll a,ll b){return a/b+(a%b>0);}
inline ll cal(int x){return ask(a[x]-a[pre[x]],x-pre[x]);}
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void read(ll&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int main(){
  read(n),read(m);
  for(i=1;i<=n;i++)read(a[i]);
  for(i=1;i<=m;i++)read(b[i]),q[i]=i;
  for(i=0;i<n;i++)nxt[i]=i+1;
  for(i=1;i<=n;i++)pre[i]=i-1,Q.push(P(a[i]-a[i-1],i));
  for(i=0;i<=n;i++)w[i]=1;
  sort(q+1,q+m+1,cmp);
  for(i=1;i<=m;i++){
    lim=b[q[i]];
    while(!Q.empty()){
      P t=Q.top();
      if(t.first>lim)break;
      Q.pop();
      x=t.second;
      if(!w[x])continue;
      if(cal(x)!=t.first)continue;
      k=w[x];
      cur-=1LL*k*a[x];
      cnt-=1LL*k*(k-1);
      y=pre[x];
      k=w[y];
      cur-=1LL*k*a[y];
      cnt-=1LL*k*(k-1);
      w[y]+=w[x];
      w[x]=0;
      k=w[y];
      cur+=1LL*k*a[y];
      cnt+=1LL*k*(k-1);
      nxt[y]=x=nxt[x];
      if(!x)continue;
      pre[x]=y;
      Q.push(P(cal(x),x));
    }
    ans[q[i]]=cur+cnt/2*lim;
  }
  for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
}