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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;

struct client
{
	int start, offset, count, value;
	client(int a,int b,int c, int d):
		start(a),
		offset(b),
		count(c),
		value(d)
	{
		
	}
};

int n,m;
list<client> L;
vector<pair<int,int> > vv;
vector<long long> vvv;
vector<long long> w;

void print()
{
	for(const auto& x : L)
	{
		cout << x.start << " " << x.offset << " " << x.count << " " << x.value << endl;
	}
	cout <<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	int x,value,res;
	list<client>::iterator it;
	list<client>::iterator nextIt;
	list<client>::iterator prevIt;

	cin >>n>>m;
	client prev(0,0,1,0);
	for(int i=0;i<n;i++)
	{
		cin >>x;
		if(L.size()>0 && L.back().start==x)
		{
			L.back().count++;
		}			
		else
		{	prev.offset=x-prev.start;
			prev.start=x;
		}
		L.push_back(prev);
	}
	for(int i=0;i<m;i++)
	{
		cin >>x;
		vv.push_back(make_pair(x,i));
		vvv.push_back(0);
		w.push_back(0);
	}
	sort(vv.begin(),vv.end());
	for(int i=0;i<m;i++)
	{
		value=vv[i].first;
		if(i>0) value-=vv[i-1].first;
		res=0;
		it = L.begin();
		
		while(it!=L.end())
		{
			if(it->offset < value)
			{
				x = value - it->offset;
				it->start += x;
				it->value +=it->count*x;
				it->value +=value*((it->count*(it->count-1))/2);
				cout <<it->count*x<<endl;
				cout << value*((it->count*(it->count-1))/2)<<endl;
				it->offset = 0;
				nextIt=it;
				nextIt++;
				res+=it->value;
				if(nextIt!=L.end())
				{
					nextIt->offset -= x + value*(it->count-1);
				}
				if(it != L.begin())
				{
					prevIt->count+=it->count;
					prevIt->value += it->value;
					L.erase(it);
					it=prevIt;
				}
			}
			else
			{
				it->offset-=value;
				x=value*((it->count*(it->count-1))/2);
				it->value+=x;
				res+=it->value;
				nextIt=it;
				nextIt++;
				if(nextIt!=L.end())
				{
					nextIt->offset -= x;
				}
			}

			prevIt=it;
			it++;
		}
		w[i]=res;
	}
	for(int i=0;i<m;i++)
	{
		vvv[vv[i].second]=w[i];
	}
	for(int i=0;i<m;i++)
	{
		cout <<vvv[i]<<endl;
	}
	
}