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 <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
#define PII pair<long long, long long>
#define PIP pair<long long, PII>
#define pb push_back
#define MP make_pair
#define ll long long
#define int long long

int n,m;
ll poczatek[300000];
ll przyrost[300000];
ll dozlaczenia[300000];
ll typki[300000];
ll answer[300000];
ll pref[300000];
int last[300000];
int R[300000];
priority_queue< PIP, vector<PIP>, greater<PIP> >Q;
vector<PII>V;
void read(){
    cin>>n>>m;
    typki[1] = 1;
    last[1] = 1;
    R[1] = 1;
    for(int i=2;i<=n+1;i++){
        cin>>poczatek[i];
        pref[i] = pref[i-1] + poczatek[i];
        typki[i] = 1;
        dozlaczenia[i] = poczatek[i] - poczatek[i-1];
        R[i] = i;
        last[i] = i;
        Q.push( MP( dozlaczenia[i], MP(i-1,i) ) );
    }
    for(int i=0;i<m;i++){
        int q;
        cin>>q;
        V.pb(MP(q,i));
    }
    sort(V.begin(),V.end());
}

int find(int a){
    if( R[a] != a )
        R[a] = find(R[a]);
    return R[a];
}

void solve(){
    ll tim = 0, new_tim = 0, plus = 0, new_plus = 0, res = 0;
    int it = 0;
    int xx=0;
    while(!Q.empty()){
        while( it < (int)V.size() && Q.top().first > V[it].first){
            ll q = V[it].first;
            int nr = V[it].second;
            answer[nr] = (q-tim)*plus + res;
            //cout<<nr<<" ans "<<answer[nr]<<endl;
            it++;
        }
        new_tim = Q.top().first;
        while( !Q.empty() && Q.top().first <= new_tim ) {
            //ll tmp_tim = Q.top().first;
            int a = Q.top().second.first;
            int b = Q.top().second.second;
            Q.pop();
            if( find(a) == a && find(b) == b ){
                //cout<<a<< " LACE "<<b<<endl;
                res -= poczatek[a] * typki[a] + przyrost[a] * tim - pref[last[a]] + pref[a-1];
                res -= poczatek[b] * typki[b] + przyrost[b] * tim - pref[last[b]] + pref[b-1];
                R[b] = a;
                last[a] = last[b];
                typki[a] += typki[b];
                plus -= przyrost[a];
                plus -= przyrost[b];
                przyrost[a] = ((typki[a]-1)*typki[a])/2;
                new_plus += przyrost[a];
                res += poczatek[a] * typki[a] + przyrost[a] * new_tim - pref[last[a]] + pref[a-1];
                //cout<<res<<" res"<<endl;
                b = last[a]+1;
                if( b <= n+1 ){
                    ll licznik = poczatek[b] - new_tim - (poczatek[a] + new_tim * ( typki[a] - 1 ) );
                    ll mianownik = typki[a];
                    ll d = licznik/mianownik;
                    if( licznik % mianownik != 0 && licznik >= 0)
                        d++;
                    Q.push(MP(new_tim+d,MP(a,b)));
                    //cout<<licznik<<" lm "<<mianownik<<endl;
                    //cout<<a<<" ab "<<b<<" "<<new_tim+d<<endl;
                }

            }
        }
        res += (new_tim-tim)*plus;
        plus += new_plus;
        tim = new_tim;
        new_plus = 0;
        xx++;
        //cout<<res<<"RES"<<endl;
        //cout<<endl;
    }
    for(;it<(int)V.size();it++){
        ll q = V[it].first;
        int nr = V[it].second;
        answer[nr] = (q-tim)*plus + res;
    }
}

void write(){
    for( int i = 0; i < m; i++ ){
        cout<<answer[i]<<endl;
    }
}
main(){
    ios_base::sync_with_stdio(false);
    read();
    solve();
    write();
}