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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
#define ll long long
#define PB push_back
#define MP make_pair
using namespace std;

const int M = 200 * 1000 + 7;
const ll zero = 0;

struct Lista
{
    ll pocz , konc;
    ll czas;
    int l_wsk , p_wsk;
};

ll l_pref[ M ];
ll t_pref[ M ];
pair < ll , int > tostery[ M ];
Lista lista[ M ];

set < pair < ll , int > > kolejka;
ll wartosc[ M ];
ll ans[ M ];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

    int n , m;
    cin >> n >> m;
    for( int i = 1 ; i <= n ; i++ )
    {
        ll t;
        cin >> t;
        lista[ i ].pocz = i , lista[ i ].konc = i;
        lista[ i ].czas = t;
        lista[ i ].l_wsk = i - 1 , lista[ i ].p_wsk = i + 1;
    }
    lista[ 1 ].l_wsk = -1 , lista[ n ].p_wsk = -1;
    for( int i = 1 ; i <= n - 1 ; i++ )
    {
        ll t1 = lista[ i ].czas , t2 = lista[ i + 1 ].czas;
        kolejka.insert( MP( t2 - t1 , i + 1 ) );
        wartosc[ i + 1 ] = t2 - t1;
        //cout << "Polacze " << i << " z " << i + 1 << " kiedy d > " << t2 - t1 << endl;
    }
    kolejka.insert( MP( lista[ 1 ].czas , 1 ) );
    wartosc[ 1 ] = lista[ 1 ].czas;

    for( ll i = 1 ; i <= n ; i++ ) l_pref[ i ] = l_pref[ i - 1 ] + i;
    for( ll i = 1 ; i <= n ; i++ ) t_pref[ i ] = t_pref[ i - 1 ] + lista[ i ].czas;

    /*cout << "*** l_pref ***" << endl;
    for( ll i = 1 ; i <= n ; i++ ) cout << l_pref[ i ] << " ";
    cout << endl;
    cout << "*** t_pref ***" << endl;
    for( ll i = 1 ; i <= n ; i++ ) cout << t_pref[ i ] << " ";
    cout << endl << endl;*/

    for( int i = 0 ; i < m ; i++ )
    {
        ll d;
        cin >> d;
        tostery[ i ] = MP( d , i );
    }
    sort( tostery , tostery + m );
    ll razy = 0 , stala = 0;
    for( int i = 0 ; i < m ; i++ )
    {
	//cout << "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" << endl;
        ll d = tostery[ i ].first;
        int ind = tostery[ i ].second;
        while( !kolejka.empty() && d > kolejka.begin() -> first)
        {
            int wsk = kolejka.begin() -> second;
            kolejka.erase( kolejka.begin() );
            int poprz = lista[ wsk ].l_wsk , nxt = lista[ wsk ].p_wsk;
            //cout << "Lacze " << poprz << " z " << wsk << endl;
            if( poprz == -1 )
            {
                ll i = lista[ wsk ].pocz , j = lista[ wsk ].konc;
                razy -= l_pref[ j - i ];
                stala += t_pref[ j ] - t_pref[ i ] - ( j - i ) * lista[ wsk ].czas;

		i = 0;
                razy += l_pref[ j ];
                stala -= t_pref[ j ];
                lista[ wsk ].pocz = 0;
                lista[ wsk ].czas = 0;
            	if( nxt != -1 )
            	{
               	    kolejka.erase( MP( wartosc[ nxt ] , nxt ) );
                    wartosc[ nxt ] = max( zero , lista[ nxt ].czas / ( j + 1 ) );
                    kolejka.insert( MP( wartosc[ nxt ] , nxt ) );
            	}
            }
            else
            {
                /// Usuwanie z ( wsk - 1 )
                ll i = lista[ poprz ].pocz , j = lista[ poprz ].konc;
                razy -= l_pref[ j - i ];
                stala += t_pref[ j ] - t_pref[ i ] - ( j - i ) * lista[ poprz ].czas;
                //cout << "Po usunieciu ( wsk - 1 ) : " << razy << " , " << stala << endl;
                /// Usuwanie z ( wsk )
                i = lista[ wsk ].pocz ; j = lista[ wsk ].konc;
                razy -= l_pref[ j - i ];
                stala += t_pref[ j ] - t_pref[ i ] - ( j - i ) * lista[ wsk ].czas;
                //cout << "Po usunieciu ( wsk ) : " << razy << " , " << stala << endl;
                /// Dodawanie z ( wsk - 1 , wsk )
                i = lista[ poprz ].pocz , j = lista[ wsk ].konc;
                razy += l_pref[ j - i ];
                stala -= t_pref[ j ] - t_pref[ i ] - ( j - i ) * lista[ poprz ].czas;

                lista[ wsk ].pocz = lista[ poprz ].pocz;
                lista[ wsk ].l_wsk = lista[ poprz ].l_wsk;
                lista[ wsk ].czas = lista[ poprz ].czas;
                if( lista[ poprz ].l_wsk != -1 ) lista[ lista[ poprz ].l_wsk ].p_wsk = wsk;
                if( kolejka.find( MP( wartosc[ poprz ] , poprz ) ) != kolejka.end() )
                {
                    kolejka.erase( MP( wartosc[ poprz ] , poprz ) );
                    wartosc[ wsk ] = wartosc[ poprz ];
                    kolejka.insert( MP( wartosc[ wsk ] , wsk ) );
                }
                if( nxt != -1 )
                {
                    kolejka.erase( MP( wartosc[ nxt ] , nxt ) );
                    wartosc[ nxt ] = max( zero , ( lista[ nxt ].czas - lista[ wsk ].czas ) / ( j - i + 1 ) );
                    kolejka.insert( MP( wartosc[ nxt ] , nxt ) );
                    lista[ nxt ].l_wsk = wsk;
                }
            }
        }
        //cout << razy << " , " << stala << endl;
        ans[ ind ] = d * razy + stala;
    }
    for( int i = 0 ; i < m ; i++ )
    {
       	cout << ans[ i ] << '\n';
    }
    return 0;
}