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
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct kubek
{
    int last;
    int next;
    int prev;
    int step;
    long long siz;
};

kubek tab[200001];

ll inf = ll(1e9) * 1e9;
ll ret[1000009];
ll help[1000001];

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    help[1] = 0;
    for(int i=2;i<2*n;i++)
        help[i] = help[i-1] + i - 1;
    ll prev = 0;
    priority_queue<pair<ll, int> > events;
    for(int i=0;i<n;i++)
    {
        ll tmp;
        scanf("%lld",&tmp);
        tab[i].last = 0;
        tab[i].next = i+1;
        tab[i].prev = i-1;
        tab[i].step = 1;
        tab[i].siz = tmp - prev;
        prev = tmp;
        events.push(make_pair(-(tab[i].siz+1), i));
    }
    tab[n].last = 0;
    tab[n].next = n+1;
    tab[n].prev = n-1;
    tab[n].step = 1;
    tab[n].siz = inf;
    int maksQ = 0;
    for(int i=0;i<m;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        maksQ = max(maksQ, tmp);
        events.push(make_pair(-tmp, -i-1));
    }

    ll odp = 0;
    ll inc = 0;
    for(int i=1;i<=maksQ;i++)
    {
        tab[n].siz = inf;
        odp += inc;
        //cerr<<"i = "<<i<<", odp = "<<odp<<", inc = "<<inc<<endl;
        //cerr<<"pq.top = "<<events.top().first<<","<<events.top().second<<endl;
        while(events.top().first == ll(-i))
        {
            int tmp = events.top().second;
            events.pop();
            //cerr<<"pq.top = "<<events.top().first<<","<<events.top().second<<endl;
            if(tmp >= 0)
            {
                tmp = tmp;
                if(tab[tmp].next == tab[tmp].prev)
                    continue;

                int steps = i - tab[tmp].last;
                tab[tmp].last = i;
                tab[tmp].siz -= tab[tmp].step * steps;
                if(tab[tmp].siz >= 0)
                {
                    events.push(make_pair(-(tab[tmp].siz / tab[tmp].step + 1 + i),tmp));
                    continue;
                }

                int nextid = tab[tmp].next;
                int previd = tab[tmp].prev;

                odp -= tab[tmp].siz * tab[nextid].step;
                inc -= help[tab[tmp].step];
                inc -= help[tab[nextid].step];
                inc += help[tab[tmp].step + tab[nextid].step];

                if(previd > -1)
                    tab[previd].next = nextid;
                tab[nextid].prev = previd;

                tab[nextid].siz += tab[tmp].siz;
                tab[nextid].step += tab[tmp].step;
                tab[nextid].siz += tab[tmp].step * (i - tab[nextid].last);

                if(nextid <= n)
                    events.push(make_pair(-i, nextid));

                tab[tmp].prev = tab[tmp].next;

                /*
                ll rest = tab[tmp].siz % tab[tmp].step;
                if(rest == 0)
                    rest = tab[tmp].step;
                int previd = tab[tmp].prev;
                int nextid = tab[tmp].next;
                odp += rest*tab[nextid].step;
                inc ++;

                if(previd != -1)
                    tab[previd].next = nextid;
                tab[nextid].prev = previd;

                ll steps = tab[tmp].siz / tab[tmp].step + 1;

                tab[nextid].siz -= steps * tab[nextid].step;
                tab[nextid].step += tab[tmp].step;
                if(nextid <= n && tab[nextid].siz >= 0)
                    events.push(make_pair(-(tab[nextid].siz / tab[nextid].step + 1 + i), nextid));
                else if(nextid <= n)
                    events.push(make_pair(-i, nextid));
                tab[tmp].next = tab[tmp].prev;
                */
            }
            else
            {
                //cerr<<"AAA"<<endl;
                tmp = -tmp;
                tmp --;
                ret[tmp] = odp;
            }
        }
    }

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