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

#define int long long
const int maxN = 2e5 + 10;

struct Client {
    int x, lvl;
    void get() {
        scanf("%lld", &x);
        lvl = 1;
    }
} t[maxN];

int find(int);

struct Colision {
    int i, lvl, tim;
    
    Colision(int i, int tim)
    : i(i), lvl(t[i].lvl), tim(tim) {
//         printf("Will colide %lld<%lld> with %lld at time %lld\n", i, lvl, find(i+1), tim);
    }
    
    bool operator<(Colision const& o) const {
        return tim > o.tim;
    }
};


int predict(Client const& a, Client const& b) {
    return (b.x - a.x + a.lvl - 1) / a.lvl;
}


int FU[maxN];

int find(int x) { return x == FU[x] ? x : FU[x] = find(FU[x]); }
int n, q;


struct Situation {
    int tim, con, lost, lost_lvl;
    Situation(int tim, int c, int lost, int lost_lvl)
    : tim(tim), con(c), lost(lost), lost_lvl(lost_lvl) {}
};

vector<Situation> situations;

void ask() {
    int a = -1, b = situations.size(), avg, tim;
    scanf("%lld", &tim);
    while(b - a > 1) {
        avg = (a + b) / 2;
        if(situations[avg].tim <= tim) a = avg;
        else b = avg;
    }
    Situation const& s = situations[a];
    printf("%lld\n", s.lost + s.lost_lvl * (tim - s.tim));
}

#undef int
int main() {
#define int long long
    scanf("%lld%lld", &n, &q);

    t[0].lvl = 1;
    t[0].x = 0;
    for(int i = 1; i <= n; ++i) {
        t[i].get();
        FU[i] = i;
    }
    FU[n + 1] = n + 1;
    
    priority_queue<Colision> col;
    for(int i = 0; i < n; ++i)
        col.emplace(i, predict(t[i], t[i+1]));

    situations.emplace_back(0, n + 1, 0, 0);

    while(!col.empty()) {
        Colision c = col.top();
        col.pop();
        if(t[c.i].lvl != c.lvl || find(c.i) != c.i)
            continue;
        int j = find(c.i + 1);
        int lost_lvl = situations.back().lost_lvl;
        int add_lost = (t[c.i].lvl * c.tim - t[j].x + t[c.i].x) * t[j].lvl;
        lost_lvl -= t[c.i].lvl * (t[c.i].lvl - 1) / 2;
        lost_lvl -= t[j].lvl * (t[j].lvl - 1) / 2;
        t[c.i].lvl += t[j].lvl;
        lost_lvl += t[c.i].lvl * (t[c.i].lvl - 1) / 2;
        FU[j] = j + 1;
        
//         printf("COLIDE %lld<%lld> with %lld at time %lld\n", c.i, c.lvl, j, c.tim);
//         printf("add_lost = %lld\n", add_lost);

        Situation const& s = situations.back();
        situations.emplace_back(c.tim, s.con - 1, (c.tim - s.tim) * s.lost_lvl + s.lost + add_lost, lost_lvl);
        if(find(c.i + 1) != n + 1)
            col.emplace(c.i, predict(t[c.i], t[find(c.i + 1)]));
    }
    for(int i = 0; i < q; ++i) ask();
}