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
#include <cstdio>
#include <utility>
#include <queue>

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define PLLII pair<long long, pair<int, int>>
#define MP(a, b, c) make_pair(a, make_pair(b, c))
#define LL long long
  
using namespace std;

const int maxn = 200010;
const int maxd = 1000010;
const LL maxt = 1000000000010L;

int n, m;
LL diff[maxn];
int d[maxn];
int topd;

priority_queue<PLLII, vector<PLLII>, greater<PLLII>> q;
int nexti[maxn];
int previ[maxn];
LL left[maxn];
LL right[maxn];
LL rightsum;
LL nextsum;
int last[maxn];
int time[maxn];
LL gnow[maxn];
LL g[maxn];

LL res[maxd];

LL powright(int right) {
  return ((LL)right*((LL)right + 1))/2;
}

int main() {
  scanf("%d%d", &n, &m);
  LL prevt = 0;
  LL currt;
  REP(i, n) {
    scanf("%lld", &currt);
    diff[i] = currt - prevt;
    prevt = currt;
    q.push(MP(diff[i], i, -1));
    left[i] = 1;
    nexti[i] = i + 1;
    previ[i] = i - 1;
    time[i] = -1;
  }
  diff[n] = 2L*maxn*maxd;
  REP(i, m) {
    scanf("%d", &d[i]);
    if (d[i] > topd) {
      topd = d[i];
    }
  }
  LL result = 0;
  int i;
  int timei;
  LL bonus;
  LL sum = 0;
  FOR(now, 0, topd) {
    result += sum;
    sum = rightsum;
    nextsum = rightsum;
    res[now] = result;
    // printf("NOW %d result %lld\n", now, result);
    while (q.top().first == (LL)now) {
      int first = q.top().first;
      i = q.top().second.first;
      timei = q.top().second.second;
      q.pop();
      if (timei < time[i]) {
        continue;
      }
      // printf("PROCESSING %lld i %d last %d (left %d, right %d) prev %d next %d\n", first, i, timei, left[i], right[i], previ[i], nexti[i]);
      diff[i] -= (left[i] + right[i])*(now - last[i]);
      // printf("diff[i] %lld\n", diff[i]);
      last[i] = now;
      diff[nexti[i]] -= (left[nexti[i]] + right[nexti[i]])*(now - last[nexti[i]]);
      // printf("diff[next[i]] %lld\n", diff[nexti[i]]);
      last[nexti[i]] = now;
      nextsum -= (gnow[i] == now) ? powright(g[i]) : powright(right[i]);
      rightsum -= powright(right[i]);
      nextsum -= powright(right[nexti[i]]);
      rightsum -= powright(right[nexti[i]]);
      // printf("BEFOR r[i] %d r[n[i]] %d\n", right[i], right[nexti[i]]);
      right[nexti[i]] += left[i] + right[i];
      // printf("r[i] %d r[n[i]] %d\n", right[i], right[nexti[i]]);
      bonus = diff[i];
      // printf("bonus %lld\n", bonus);
      nextsum += powright(bonus) + powright((gnow[i] == now) ? right[nexti[i]] - right[i] + g[i] - bonus : right[nexti[i]] - bonus);
      rightsum += powright(right[nexti[i]]);
      g[nexti[i]] = right[nexti[i]] - bonus;
      gnow[nexti[i]] = now;
      // Adjust pointers to skip the current block.
      if (previ[i] >= 0) {
        nexti[previ[i]] = nexti[i];
      }
      previ[nexti[i]] = previ[i];
      // Schedule next check.
      time[nexti[i]] = now;
      q.push(MP((LL)now + diff[nexti[i]]/(left[nexti[i]] + right[nexti[i]]), nexti[i], now));
      // printf("rightsum temp %lld\n", rightsum);
      sum = nextsum;
    }
    // printf("RIGHTSUM %lld\n", rightsum);
  }
  REP(i, m) {
    printf("%lld\n", res[d[i]]);
  }
  return 0;
}