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
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

typedef long long ll;
typedef pair<ll, int> event;

struct segment {
    ll first, evnt;
    int cnt, nekst;

    segment() {};
    segment(ll _f, ll _e, int _c, int _n) : first(_f), evnt(_e), cnt(_c), nekst(_n) {};
};

inline ll _ceil(ll a, ll b) {
    if(a % b == 0)
        return a / b;
    return a / b + 1;
}

inline ll sum_of(segment s, ll d) {
    return ll(s.cnt) * s.first + ll(s.cnt) * ll(s.cnt - 1LL) / 2LL * d;
}

inline ll growth(segment s) {
    return ll(s.cnt) * ll(s.cnt - 1LL) / 2LL;
}

ll res;
int n, m;
segment S[200007];
set<event> E;
event Q[200007];
ll fin[200007];
bool del[200007];
ll sum = 0, grows_by = 0;

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

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

    for(int i = 0 ; i < n ; i++) {
        E.insert({S[i + 1].first - S[i].first, i});
        S[i].evnt = S[i + 1].first - S[i].first;
    }

    for(int i = 0 ; i < m ; i++) {
        scanf("%lld", &Q[i].X);
        Q[i].Y = i;
    }

    sort(Q, Q + m);

    ll d = 0, prevd = 0;
    int segments_cnt = n + 1;
    for(int i = 0 ; i < m ; i++) {
        while(!E.empty() && (*E.begin()).X <= Q[i].X) {
            event e = *E.begin();
            E.erase(E.begin());
            d = e.X;

            if(d > prevd) {
               res += (d - prevd) * grows_by;
            }

            int a = e.Y;
            grows_by -= growth(S[a]);
            res -= sum_of(S[a], d);

            int b = S[a].nekst;

            while(S[a].first + d * (S[a].cnt - 1) >= S[b].first - d) {
                E.erase({S[b].evnt, b});

                del[b] = true;
                grows_by -= growth(S[b]);
                res -= sum_of(S[b], d);

                segments_cnt--;

                S[a].cnt += S[b].cnt;
                S[a].nekst = S[b].nekst;
                b = S[a].nekst;
                if(b == n + 1)
                    break;
            }

            grows_by += growth(S[a]);
            res += sum_of(S[a], d);
            if(b != n + 1) {
                E.insert({_ceil(S[b].first - d - S[a].first - d * (S[a].cnt - 1), S[a].cnt) + d, a});
                S[a].evnt = _ceil(S[b].first - d - S[a].first - d * (S[a].cnt - 1), S[a].cnt) + d;
            }

            prevd = d;
        }

       if(Q[i].X > prevd) {
            res += grows_by * (Q[i].X - prevd);
            prevd = Q[i].X;
       }

        fin[Q[i].Y] = res;
    }

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


    return 0;
}