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
#include <bits/stdc++.h>
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define LL long long
#define pii pair<int,int>
#define pll pair<LL,LL>
#define ALL(V) V.begin(),V.end()
#define f1(a,b) for(int a=1;a<=b;a++)
#define f0(a,b) for(int a=0;a<b;a++)
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl "\n"
using namespace std;
const int N=1e6+69, base=1024*1024;
LL n,m,czas,t[N],suf[N], rep[N],rang[N],mi[N],ma[N],tree[base*2+69],tim[N];
set <pair<LL,pll>> S;
LL test(int,int);
int re(int);
void uni(int,int);
void insert(LL,LL,LL);
LL query(int);
void dodaj(int,int,int);
void jp(int,int);
int32_t main(void) {
    boost;
    cin>>n>>m;
    f1(i,n) {
        cin>>t[i];
    }
    f0(i,N-5) {
        rang[i]=1;
        rep[i]=i;
        mi[i]=t[i];
        ma[i]=i;
        tim[i]=0;
    }
    f0(i,n) S.insert(MP(test(i,i+1),MP(i,i+1)));
    while(!S.empty()) {
        pair<LL,pll> zm=(*S.begin());
        S.erase(S.begin());
        zm.s.s=re(zm.s.s);
        zm.s.f=re(zm.s.f);
        if(zm.s.s>n) continue;
        if(re(zm.s.f)==re(zm.s.s)) continue;
        czas=max(czas,zm.f);
        uni(zm.s.f,zm.s.s);
        LL z=re(zm.s.s);
        LL jan_pawel=test(z,ma[z]+1);
        S.insert(MP(jan_pawel,MP(z,ma[z]+1)));
    }
    dodaj(czas+1,N-7,1);
    f1(i,N-5) {
        suf[i]=suf[i-1]+query(i);
    }
    f0(i,m) {
        int a;
        cin>>a;
        cout<<suf[a]<<endl;
    }
}
void dodaj(int l, int p, int v) {
    v=re(v);
    LL ile=rang[v];
    ile*=(ile-1);
    ile/=2;
    insert(l,p,ile);
}
LL test(int a, int b) {
    a=re(a);
    b=re(b);
    LL l=mi[a];
    LL p=mi[b];
    p-=l;
    LL k=rang[a];
    p=(p+k-1)/k;
    return p;
}
int re(int v) {
    if(rep[v]!=v) rep[v]=re(rep[v]);
    return rep[v];
}
void uni(int a,int b) {
    a=re(a);
    b=re(b);
    if(a==b) return;
    jp(a,b);
    if(rang[a]>rang[b]) swap(a,b);
    dodaj(tim[b],czas,b);
    dodaj(tim[a],czas,a);
    rep[a]=b;
    rang[b]+=rang[a];
    mi[b]=min(mi[a],mi[b]);
    ma[b]=max(ma[a],ma[b]);
    tim[b]=czas+1;
}
void jp(int a, int b) {
    a=re(a);
    b=re(b);
    LL zm=mi[a];
    zm+=czas*rang[a];
    zm-=mi[b];
    zm*=rang[b];
    insert(czas,czas,zm);
}
void insert(LL l,LL p,LL war) {
    if(l>p) return;
    l+=base;
    p+=base;
    tree[l]+=war;
    if(l!=p) tree[p]+=war;
    while(l+1<p) {
        if(l%2==0) tree[l+1]+=war;
        if(p%2==1) tree[p-1]+=war;
        p/=2;
        l/=2;
    }
}
LL query(int v) {
    v+=base;
    LL ret=0;
    while(v) {
        ret+=tree[v];
        v/=2;
    }
    return ret;
}