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
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define PLL pair <long long, long long>
#define fi first
#define se second
const int MX = 1e6 + 10;
const int mxn = 2e5 + 10;

int n, m;
LL t[mxn], roz[mxn], pref[mxn];
int d[mxn], id[mxn];

LL min_d[mxn];

vector <int> kolej[MX];
LL suma, curr;
LL zas[mxn];
LL wyn[MX];

void wczytaj()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &t[i]);
		roz[i] = t[i] - t[i - 1];
		pref[i] = roz[i] + pref[i - 1];
	}
	for(int i = 1; i <= m; i++)
		scanf("%d", &d[i]);	
}

bool mn_ro(PLL a, PLL b)
{
	return a.fi * b.se <= a.se * b.fi;
}

bool mn(PLL a, PLL b)
{
	return a.fi * b.se < a.se * b.fi;
}


void policz_id()
{
	for(int i = 1; i <= n; i++)
	{
		int v = i - 1;
		PLL min_sr = {roz[i], 1};
		while(v != 0)
		{
			int nast = id[v];
			if(mn({pref[i] - pref[v], i - v}, {pref[i] - pref[nast], i - nast}))
				break;
			
			v = nast;
		}
		id[i] = v;
	}
	//for(int i = 1; i <= n; i++)printf("id[%d] = %d\n", i, id[i]);
}

void policz_min_d()
{
	for(int i = 1; i <= n; i++)
	{
		min_d[i] = (pref[i] - pref[id[i]]) / ((LL)i - (LL)id[i]) + 1LL;
		if(min_d[i] < (LL)MX)
			kolej[min_d[i]].push_back(i);
	}
	for(int i = 0; i < MX; i++)
		reverse(kolej[i].begin(), kolej[i].end());
	
	//for(int i = 1; i <= n; i++)	printf("min_d[%d] = %lld\n", i, min_d[i]);
}

inline LL dwu(LL a)
{
	return a * (a + 1LL) / 2LL;
}

void policz_wyn()
{
	for(int i = 0; i < MX; i++) // KUIRWA ZAMIENIC!!!!!!!!!!!!!
	{
		for(auto j : kolej[i])
		{
			curr -= dwu(zas[j]);
			curr -= dwu(zas[id[j]]);
			
			zas[j]++;
			
			LL roznica = ((LL)i * ((LL)j - (LL)id[j]) - (pref[j] - pref[id[j]])) * zas[j]; 
			
			suma += roznica;
			
			zas[id[j]] += zas[j];
			
			curr += dwu(zas[id[j]]);
		}
		wyn[i] = suma;
		
		suma += curr;
		
	}
	
	//for(int i = 0; i < 10; i++)	{printf("wyn[%d] = %lld\n", i, wyn[i]);}
}

int main()
{
	wczytaj();
	policz_id();
	policz_min_d();
	policz_wyn();
	
	for(int i = 1; i <= m; i++)
		printf("%lld\n", wyn[d[i]]);
}