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
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAX = 200000;
const ll inf = 1000000000000000000ll;

int s[MAX+1];
int sz[MAX+1];
ll sum[MAX+1];
bool vis[MAX+1];

int findset(int x) {
  return x == s[x] ? x : s[x] = findset(s[x]);
}

bool link(int x, int y) {
  x = findset(x);
  y = findset(y);
  if (x == y) return false;
  s[x] = y;
  sz[y] += sz[x];
  return true;
}

struct G {
  int id;
  ll t;
  bool operator<(G const& rhs) const {
    return t > rhs.t;
  }
};

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  vector<ll> T(n+1);
  sz[0] = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &T[i]);
    s[i] = i;
    sz[i] = 1;
    sum[i] = sum[i-1] + T[i];
  }
  priority_queue<G> Q;
  for (int i = 0; i < n; i++) {
    Q.push({i, T[i+1] - T[i]});
  }
  Q.push({n, inf});
  vector<ll> res(1000001);
  ll add = 0;
  ll r = 0;
  for (int i = 1; i < (int)res.size(); i++) {
    while (!Q.empty() && Q.top().t < i) {
      auto g = Q.top();
      Q.pop();
      if (vis[g.id]) continue;
      // printf("get %d %lld\n", g.id, g.t);
      vis[g.id] = true;
      int x = findset(g.id);
      if (x == n) continue;
      int y = findset(g.id + 1);
      add -= (ll)sz[x] * (sz[x] - 1) / 2;
      add -= (ll)sz[y] * (sz[y] - 1) / 2;
      r -= sum[x] - sum[x - sz[x]] - (ll)(sz[x] - 0) * T[x - sz[x] + 1];
      r -= sum[y] - sum[y - sz[y]] - (ll)(sz[y] - 0) * T[y - sz[y] + 1];
      // printf("link %d %d\n", x, y);
      link(x, y);
      if (y != n) {
        ll v = (T[y+1] - T[y - sz[y] + 1]) / (sz[y] + 0);
        // printf("push %d %lld\n", y, (T[findset(y+1)] - T[x]) / (sz[y] - 0));
        Q.push({y, v});
      }
      add += (ll)sz[y] * (sz[y] - 1) / 2;
      r += sum[y] - sum[y - sz[y]] - (ll)(sz[y] - 0) * T[y - sz[y] + 1];
    }
    // printf("%d: %lld %lld\n", i, add, r);
    res[i] = add * i - r;
  }
  while (k--) {
    int d;
    scanf("%d", &d);
    printf("%lld\n", res[d]);
  }
  printf("\n");
  return 0;
}