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
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

const int N = 2e5;
const int M = 1e6;

long long t[N + 7];
bool akt[N + 7];
int ile[N + 7];
int n, m;
long long sumap = 0;

struct ev {
    long long ti;
    int a, b;
    ev() : ti(0), a(0), b(0) {}
    ev(long long ti, int a, int b) : ti(ti), a(a), b(b) {}
    bool operator()(ev A, ev B) {
        if(A.ti == B.ti) {
            if(A.a == B.a) return A.b < B.b;
            else return A.a < B.a;
        }
        else return A.ti < B.ti;
    }
};

set <ev, ev> T;
set <int> S;

long long res[M + 7];

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    n++;
    for(int i = 2; i <= n; ++i) {
        cin >> t[i];
        sumap += t[i];
    }
    t[1] = 0;
    
    for(int i = 1; i <= n; ++i) {
        S.insert(i);
        akt[i] = 1;
        ile[i] = 1;
        
        if(i < n) {
            T.insert(ev(t[i + 1] - t[i], i, i + 1));
        }
    }       
    
    long long sum1 = 0;
    long long sum2 = 0;
    
    for(int i = 1; i <= n; ++i) sum2 += t[i];
    
    for(int i = 0; i <= M; ++i) {
        while(!T.empty() && (*T.begin()).ti == i) {
            int a = (*T.begin()).a;
            int b = (*T.begin()).b;
            T.erase(T.begin());
         
            if(!akt[a] || !akt[b]) continue;
            
            sum1 -= ((long long) ile[b] * (ile[b] - 1)) / 2;
            sum1 -= ((long long) ile[a] * (ile[a] - 1)) / 2;
            sum2 -= t[b] * ile[b];
            sum2 -= t[a] * ile[a];
            
            ile[a] += ile[b];
            akt[b] = 0;
            
            sum1 += ((long long) ile[a] * (ile[a] - 1)) / 2;
            sum2 += t[a] * ile[a];
            
            S.erase(b);
            auto it = S.find(a);
            it++;
            if(it != S.end()) {
                int bp = *it;
                long long nt = t[bp] - t[a] + ile[a] - 1;
                nt /= ile[a];
                T.insert(ev(nt, a, bp));
            }
        }
        
        res[i] = sum1 * i + sum2;
    }
    
    for(int i = 1; i <= m; ++i) {
        int q;
        cin >> q;
        cout << res[q] - sumap << '\n';
    }   
    return 0;
}