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
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int MAX_N = 200007;
//const int MAX_D = 17;
const int MAX_D = 1000007;

typedef long long LL;

LL t[MAX_N];
int d[MAX_N];
LL size[MAX_N]; // size of i-th waiting group (index of group is the number of its first client)
//LL sum[MAX_N]; // sum of times of arrivals with respect to 1. client (for the i-th group)
bool inactive[MAX_N];

vector<int> conflict[MAX_D];


LL R[MAX_D];

int n, m;

LL result1 = 0;
LL result2 = 0;


LL wTime(LL group_size) {
    return group_size * (group_size - 1) / 2;
}


void merge (int group) {
    int next_group = group + size[group];
    inactive[next_group] = true;

    result1 -= wTime(size[group]) + wTime(size[next_group]);
    size[group] += size[next_group];
    result1 += wTime(size[group]);

    result2 += size[next_group] * (t[next_group] - t[group]);

    // Only for debugging purposes
//    sum[group] += sum[next_group] + size[next_group] * (t[next_group] - t[group]);
}


int main()
{
    scanf("%d %d", &n, &m);

    t[0] = 0L;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &t[i]);
    }

    for (int i = 0; i < m; ++i) {
        scanf("%d", &d[i]);
    }

    for (int i = 0; i <= n; ++i) {
        size[i] = 1;
//        sum[i] = 0;
    }

    for (int i = 0; i < n; ++i) {
        LL time = t[i+1] - t[i];
        if (time < MAX_D) {
            conflict[time].push_back(i);
        }
    }


    for (int D = 0; D < MAX_D; ++D)
    {
//        printf("D: %d\n", D);

        sort(conflict[D].begin(), conflict[D].end());

        while (!conflict[D].empty())
        {
            int group = conflict[D].back();
            conflict[D].pop_back();

            if (inactive[group]) {
                continue;
            }

            int next_group;

            do {
                merge(group);
                next_group = group + size[group];
            } while (next_group <= n
                     && t[group] + size[group] * D >= t[next_group]);

            LL conflict_d = (t[next_group] - t[group]) / size[group] + 1;

            if (conflict_d < MAX_D) {
                conflict[conflict_d].push_back(group);
            }
        }

        R[D] = result1 * D - result2;

//        printf("R[%d]: %lld\n", D, R[D]);
//        printf("R1: %lld R2: %lld\n", result1, result2);
    }

    for (int i = 0; i < m; ++i) {
        printf("%lld\n", R[d[i]]);
    }

    return 0;
}