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
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int M = 200010;
set< pair< long long, int > > secik;
set< pair< long long, int > >::iterator it;
long long n, m, par[M], i[M], sum[M], pocz[M], nex[M], need[M], x;
long long Sum, Sum2, Ile, len, id, ans[M], inf = 1e18;
vector< pair< long long, int > > tab;

long long d ( long long x )
{
	return x*(x+1) / 2;
}
int find( int x )
{
	if( x != par[x] )par[x] = find( par[x] );
	return par[x];
}
void uni( int x, int y )
{
	x = find(x);
	y = find(y);
	if( x == y )return;
	if( i[x] < i[y] )swap( x, y );
	par[y] = x;
	secik.erase( make_pair(need[x], x) );
	secik.erase( make_pair(need[y], y) );
	Sum2 -= (i[x]-1)*pocz[x];
	Sum2 -= (i[y]-1)*pocz[y];
	if( x < y )
	{
		sum[x] += sum[y] + pocz[y];
		Sum += pocz[y];
		nex[x] = nex[y];
	}
	else
	{
		sum[x] += sum[y] + pocz[x];
		Sum += pocz[x];
		pocz[x] = pocz[y];
	}
	Ile -= d(i[x]-1);
	Ile -= d(i[y]-1);
	i[x] += i[y];
	Ile += d(i[x]-1);
	Sum2 += (i[x]-1)*pocz[x];
	
	need[x] = ( pocz[find(nex[x])] - pocz[x] ) / i[x];
	secik.insert( make_pair( need[x], x ) );
	if( len > need[x] )uni( x, nex[x] );
}
int main()
{
	ios_base::sync_with_stdio( 0 );
	cin.tie( 0 );
	cin>>n>>m;
	for( int a = 0; a <= n+1; a++ )
	{
		par[a] = a;
		i[a] = 1;
		sum[a] = 0;
		nex[a] = a+1;
		
	}
	
	pocz[n+1] = inf;
	long long las = 0;
	pocz[0] = 0;
	
	for( int a = 1; a <= n; a++ )
	{
		cin>>x;
		pocz[a] = x;
		need[a-1] = x - las;
		secik.insert( make_pair( x - las, a-1 ) );
		las = x;
	}
	
	for( int a = 1; a <= m; a++ )
	{
		cin>>x;
		tab.push_back( make_pair( x, a ) );
	}
	sort( tab.begin(), tab.end() );
	
	for( int a = 0; a < tab.size(); a++ )
	{
		len = tab[a].first;
		id = tab[a].second;
		while( 1 )
		{
			if( secik.size() == 0 )break;
			it = secik.begin();
			if( it->first >= len )break;
			uni( it->second, nex[it->second] );
		}
		ans[id] = Sum2 + len * Ile - Sum;
	}
	for( int a = 1; a <= m; a++ )cout<<ans[a]<<endl;
	return 0;
}