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
121
122
123
124
#include <bits/stdc++.h>
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

#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)-1; i>=(b); --i)

#define pb push_back
#define mp make_pair
#define st first
#define nd second

const int MOD = 1000000007;

typedef pair<LL, LL> PLL;

struct Group {
  LL time;
  LL size;
};

bool operator<(const Group& g1, const Group& g2) {
  return g1.time < g2.time;
}

inline LL get_cost_per_second(const Group& group) {
  return group.size * (LL)(group.size - 1) / 2;
}

inline LL get_meet_time(const Group& g1, const Group& g2) {
  return (g2.time - g1.time) / g1.size + 1;
}

LL result[300000];

int main() {
  // ios_base::sync_with_stdio(0);

  int N, M;
  scanf("%d%d", &N, &M);
  map<LL, int> initial_groups_map;
  REP(i,N) {
    LL t;
    scanf("%lld", &t);
    ++initial_groups_map[t];
  }
  ++initial_groups_map[0];

  vector<Group> initial_groups;
  for (auto p: initial_groups_map) {
    initial_groups.pb({p.st, p.nd});
  }

  priority_queue<PLL, vector<PLL>, greater<PLL>> events;
  LL cost_per_second = 0;
  set<Group> groups;

  REP(i,initial_groups.size()) {
    cost_per_second += get_cost_per_second(initial_groups[i]);
    groups.insert(initial_groups[i]);

    if (i + 1 < initial_groups.size()) {
      LL meet_time = get_meet_time(initial_groups[i], initial_groups[i+1]);
      events.push({meet_time, -initial_groups[i].time});
    }
  }

  REP(i,M) {
    int d;
    scanf("%d", &d);
    events.push({d, i+1});
  }

  LL offset = 0;
  while (!events.empty()) {
    PLL event = events.top();
    events.pop();

    // printf("EVENT %d %d\n", event.st, event.nd);
    // printf("%d %d\n", events.size(), groups.size());
    //printf("PER_SECOND: %lld OFFSET: %lld\n", cost_per_second, offset);

    if (event.nd > 0) {
      result[event.nd] = event.st * cost_per_second + offset;
      continue;
    }

    LL merging_group_time = -event.nd;
    set<Group>::iterator it = groups.lower_bound({merging_group_time, -1});
    if (it == groups.end() || it->time != merging_group_time) continue;

    Group g1 = *it;
    Group g2 = *(++it);
    //printf("MERGING (%lld %lld) WITH (%lld %lld)\n", g1.time, g1.size, g2.time, g2.size);

    groups.erase(g1);
    groups.erase(g2);

    Group new_group = { g1.time, g1.size + g2.size };
    cost_per_second += get_cost_per_second(new_group) - get_cost_per_second(g1) - get_cost_per_second(g2);
    offset -= (get_cost_per_second(new_group) - get_cost_per_second(g1) - get_cost_per_second(g2)) * event.st;
    offset += g2.size * (g1.time + g1.size * event.st - g2.time);

    groups.erase(g1);
    groups.erase(g2);
    it = groups.insert(new_group).st;

    set<Group>::iterator it2 = it;
    if (++it2 != groups.end()) {
      LL meet_time = get_meet_time(new_group, *it2);
      //printf("SETTING MEET TIME FOR (%lld %lld) AND (%lld %lld) to %lld\n", new_group.time, new_group.size, it2->time, it2->size, meet_time);
      events.push({meet_time, -new_group.time});
    }
  }

  assert(groups.size() == 1);
  REP(i,M) printf("%lld\n", result[i+1]);
}