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
125
126
127
128
129
130
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

#define INF 1099511627776L

struct Bag{
  long long firstPoint;
  long long amount;
  long long mergingAt;
  Bag* nextBag;
  bool active;
  bool operator<(const Bag& other) const {
      return mergingAt > other.mergingAt;
  }
  
};


struct Wrap{
  Bag* bag;
  bool operator<(const Wrap& other) const {
      return bag->mergingAt > other.bag->mergingAt;
  }
};


void updateMerging(Bag* bag){
  if(bag->nextBag == 0){
    bag->mergingAt = INF;
  } else {
    //solve p + (amount-1)k >= next->p -k
    // k(amount)>next->p - p
    // k = ceil next->p - p / amount
    //check me
    bag->mergingAt = (bag->nextBag->firstPoint - bag->firstPoint + bag->amount-1 )/bag->amount;
  }
}



long long sq(long long n){
  return n*(n+1L)/2L;
}

long long t[262144];
long long delay[1048576];

int main(){
  int n,m;
  scanf("%d%d", &n, &m);
  
  for(int i=0;i<n;++i){
    scanf("%lld", &t[i+1]);
  }
  t[0] = 0;
  long long delta = 0;
   /*build bags*/
  Bag* last = new Bag();
  last->firstPoint = t[n];
  last->amount = 1;
  last->mergingAt = INF;
  last->active = true;
  
  for(int i=n-1; i>=0; i--){
    if(last->firstPoint == t[i]){
      last->amount++;
    } else {
      Bag* tmp = new Bag();
      tmp->firstPoint = t[i];
      tmp->amount = 1;
      tmp->active = true;
      tmp->nextBag = last;
      updateMerging(last);
      delta += sq(last->amount-1);
      last = tmp;
    }
  }
  updateMerging(last);
  delta += sq(last->amount-1);

  
  /*throw stuff into priority queue*/
  priority_queue<Wrap> queue;
  while(last){
    Wrap tmp;
    tmp.bag = last;
    queue.push(tmp);

    last = last->nextBag;
  }
  
  /* find delay for each time in [1000000]*/
  delay[0] = 0;
  for(int i=1;i<1048576;++i){
    delay[i] = delay[i-1] + delta;
    while(queue.top().bag->mergingAt <= (long long)i){
      Bag* curr = queue.top().bag;
      queue.pop();
      if(!curr->active){
        continue;
      }
      Bag* next = curr->nextBag;
      delay[i] += (next->amount)*(curr->firstPoint + (curr->amount-1)*i - next->firstPoint + i);
      next->active = false;
      delta -= sq(curr->amount-1);
      delta -= sq(next->amount-1);
      curr->amount += next->amount;
      delta += sq(curr->amount-1);
      curr->nextBag = next->nextBag;
      updateMerging(curr);
      Wrap tmp;
      tmp.bag = curr;
      queue.push(tmp);
    }

  }
  
  for(int i=0;i<m;++i){
    int q;
    scanf("%d", &q);
    printf("%lld\n", delay[q]);
  }
  return 0;
}