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 <vector>
#include <queue>
#include <climits>
#include <iostream>
#include <algorithm>
#ifndef d
#define d(...)
#endif
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename t>using V=vector<t>;

constexpr int MaxD = 1e6;
constexpr ll INF = LLONG_MAX;

struct Ev
{
    ll t; int l, p; int siz; bool fl;
    Ev() : t( 0 ), l( -1 ), p( -1 ), siz( 0 ), fl( false ) {}
    Ev( ll t, int l, int p ) : t( t ), l( l ), p( p ), siz( 0 ), fl( false ) {}
};

int czas = 0;
ll res = 0;
ll curr = 0;
int n, q;
V< Ev > tab;
V< ll > odp ( MaxD + 1 );
priority_queue< pair< ll, int >, V< pair< ll, int > >,
greater< pair< ll, int > > > Q;

inline ll licz ( int n )
{
    return (ll)n * (ll)( n + 1 ) / 2;
}

void dodaj ( int ind )
{
    if ( tab[ind].l == -1 )
        return;
    int l = tab[ind].l;
    ll odl = tab[ind].t - tab[l].t;
    d( "dodaj: " << odl / ( tab[l].siz + 1 ) + 1 << ' ' << ind << '\n' );
    Q.push( { odl / ( tab[l].siz + 1 ) + 1, ind } );
}

void polacz ( int ind )
{
    if ( tab[ind].fl == true )
        return;
    d( "polacz: " << ind << ' ' << czas << '\n' );
    int l = tab[ind].l;
    ll przek = tab[l].t + (ll)czas * ( tab[l].siz + 1 ) - tab[ind].t;
    res += przek * ( tab[ind].siz + 1 );
    curr -= licz( tab[ind].siz );
    curr -= licz( tab[l].siz );
    tab[l].siz += tab[ind].siz + 1;
    curr += licz( tab[l].siz );
    tab[l].p = tab[ind].p;
    tab[tab[ind].p].l = l;
    dodaj( tab[l].p );
    tab[ind].fl = true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    tab.resize( n + 2 );
    tab[0] = Ev( 0, -1, 1 );
    tab[n + 1] = Ev( INF, n, -1 );
    Q.push( { INF, -1 } );
    for ( int i = 1; i <= n; ++i )
    {
        ll t; cin >> t;
        tab[i] = Ev( t, i - 1, i + 1 );
    } 
    for ( int i = 1; i <= n; ++i )
        dodaj( i );
    for ( int i = 0; i <= MaxD; ++i )
    {
        res += curr;
        while ( Q.top().first <= i )
        {
            polacz( Q.top().second ); 
            Q.pop();
        }
        ++czas;
        odp[i] = res;
    }
    while ( q-- ) 
    {
        int p; cin >> p;
        cout << odp[p] << '\n';
    }
}