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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
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 mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=201000;
ll k,c,t[N],s[N],boom[N],ret[N];
vector<PII> e;
set<pair<ll,int> > ev;
set<PII> seg;
int n,m,d;
void add(int l,int r) {
	k+=(ll)(r-l)*(r-l+1)/2;
	c+=t[l]*(r-l+1)-(s[r]-s[l-1]);
}
void del(int l,int r) {
	k-=(ll)(r-l)*(r-l+1)/2;
	c-=t[l]*(r-l+1)-(s[r]-s[l-1]);	
}
void gao(int id) {
	auto it=seg.lower_bound(mp(id,id)),pit=it;
	++pit; auto nit=pit; ++nit;
	del(it->fi,it->se);
	del(pit->fi,pit->se);
	add(it->fi,pit->se);
	int l=it->fi,r=pit->se,rr=nit->fi;
	int md=pit->fi;
	ev.erase(mp(boom[md],md));
	seg.erase(it);
	seg.erase(pit);
	seg.insert(mp(l,r));
	boom[l]=(t[rr]-t[l])/(rr-l);
	ev.insert(mp(boom[l],l));
}
int main() {
	scanf("%d%d",&n,&m);
	t[1]=0;
	rep(i,2,n+2) scanf("%lld",t+i),s[i]=s[i-1]+t[i];
	++n;
	rep(i,0,m) {
		scanf("%d",&d);
		e.pb(mp(d,i));
	}
	sort(all(e));
	t[n+1]=1ll<<60;
	seg.insert(mp(n+1,n+1));
	rep(i,1,n+1) {
		add(i,i);
		seg.insert(mp(i,i));
		boom[i]=t[i+1]-t[i];
		ev.insert(mp(boom[i],i));
	}
	rep(i,0,m) {
		while (ev.begin()->fi<e[i].fi) {
			int id=ev.begin()->se;
			ev.erase(ev.begin());
			gao(id);
		}
		ret[e[i].se]=k*e[i].fi+c;
	}
	rep(i,0,m) printf("%lld\n",ret[i]);
}