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 #include #include #include 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 T; set 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; }