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>
using namespace std;

#ifndef _WIN32
    #define getchar getchar_unlocked
#endif

#define MP make_pair
#define PB push_back
#define ST first
#define ND second

typedef long long int LLI;
typedef unsigned long long int LLU;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<long long int, long long int> pll;
typedef vector<int> vi;

template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',') cerr<<*sdbg++;
  cerr<<"="<<h<<",";
  _dbg(sdbg+1, a...);
}
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

const LLI INF = 3e12;
const int MX = 200007;
set<pll> zbior; //pozycja, nr
set<pll> kol; //moment, nr
LLI poz[MX]; int ilosc[MX];
LLI wyn[MX*5];
int n, kek;
LLI odp, dod;

LLI policz(int x){ if(x == n + 2) return -1;
	LLI a = poz[x]; 
	LLI b = (*(next(zbior.find({poz[x], x})))).ST;
	return (b - a + ilosc[x] - 1)/ilosc[x];
}

LLI wzorek(int nr){
	return poz[nr]*ilosc[nr] + (LLI(kek)*(ilosc[nr])*(ilosc[nr]-1))/2;
}

LLI wzorek2(int nr){
	return LLI(ilosc[nr])*(ilosc[nr]-1)/2;
}

LLI wzorek1(int nr){
	return poz[nr]*ilosc[nr];
}

void merge(int nr, bool b){
	auto it = (next(zbior.find({poz[nr], nr})));
	int nast = (*it).ND;
	if(b){
		odp -= wzorek1(nr); odp -= wzorek1(nast); dod -= wzorek2(nr); dod -= wzorek2(nast);
	}
	kol.erase({policz(nast), nast});
	zbior.erase(it);
	ilosc[nr] += ilosc[nast];
	if(b){
		odp += wzorek1(nr); dod += wzorek2(nr);
	}
	kol.insert({policz(nr), nr});
}

int32_t main()
{
	int m; scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &poz[i]); ilosc[i] = 1;
		zbior.insert({poz[i], i}); 
	}
	zbior.insert({0, 0}); zbior.insert({-INF, n + 1}); zbior.insert({INF, n + 2}); poz[0] = 0; poz[n + 1] = -INF; poz[n + 2] = INF; ilosc[0] = 1; ilosc[n + 1] = 1; ilosc[n + 2] = 1;
	for(pll p : zbior){
		LLI mom = policz(p.ND); 
		if(mom != -1)	kol.insert({mom, p.ND});
	}
	for(pll p : zbior)
		if(0 <= p.ND && p.ND <= n) odp += wzorek(p.ND);
	for(int d = 0; d <= 1000000; ++d){ kek = d;
		while((*kol.begin()).ST <= d){
			int nr = (*kol.begin()).ND; kol.erase(kol.begin());
			merge(nr, 1);
		}
		wyn[d] = odp + d*dod;
	}
	for(int i = 1; i <= m; ++i){
		int x; scanf("%d", &x);
		printf("%lld\n", wyn[x] - wyn[0]);
	}
}

/*
2 5
5 5
1 2 3 4 5 
*/