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
#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
const int N = 200001;
const long long INF = 1LL<<60;
using Diff = pair<long long, int>;
long long t[N], res[N];
pair<int, int> sd[N];
priority_queue<Diff, vector<Diff>, greater<Diff>> diffs;
int d[N], last[N], par[N];
long long size[N];
int find(int a) { return (par[a] == a ? a : (par[a] = find(par[a]))); }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i=1; i<=n; i++) {
    size[i] = 1;
    last[i] = i;
    par[i] = i;
  }
  for (int i=1; i<=n; i++) {
    cin >> t[i];
    diffs.push({t[i] - t[i-1] + 1, i});
  }
  diffs.push({INF, -1});
  for (int i=0; i<m; i++) {
    cin >> d[i];
    sd[i] = {d[i], i};
  }
  sort(sd, sd+m);
  int answered = 0;
  long long cur = 0, total = 0, joined = 0;
  while (answered < m) {
    auto diff = diffs.top();
    diffs.pop();
    
    while (answered < m && sd[answered].first < diff.first) {
      res[sd[answered].second] = total + joined * (sd[answered].first - cur);
      answered++;
    }
    if (answered == m) break;
    
    int next_ind = find(diff.second);
    int ind = find(diff.second-1);
    if (ind == next_ind) continue;
    long long delta = diff.first - cur;
    total += delta * joined;
    
    long long start_time = t[next_ind] - (cur + delta);
    long long stop_time = t[ind] + (size[ind] - (ind!=0)) * (cur + delta);
    total += (stop_time - start_time) * size[next_ind];
    
    if (ind == 0) joined -= size[ind] * (size[ind]+1) / 2;
    else joined -= size[ind] * (size[ind]-1) / 2;
    joined -= size[next_ind] * (size[next_ind]-1) / 2;
    
    par[next_ind] = ind;
    size[ind] += size[next_ind];
    last[ind] = last[next_ind];

    if (ind == 0) joined += size[ind] * (size[ind]+1) / 2;
    else joined += size[ind] * (size[ind]-1) / 2;

    cur = diff.first;
    stop_time = t[ind] + (size[ind] - (ind!=0)) * cur;
    next_ind = last[ind]+1;
    if (next_ind <= n) {
      long long diff = t[next_ind] - cur - stop_time;
      if (diff < 0) diffs.push({cur, next_ind});
      else diffs.push({cur + diff / (size[ind]+(ind==0)) + 1, next_ind});
    }
  }
  for (int i=0; i<m; i++) cout << res[i] << "\n";
  return 0;
}