IPST58: Wreak It Ralph

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

int height[N + 1], dp[N + 1];
int nBuilding, Q;

int main(){

    scanf("%d %d", &nBuilding, &Q);
    for(int i = 1; i <= nBuilding; ++i){
        scanf("%d", &height[i]);
    }

    stack<int> stk;
    dp[1] = 0;
    stk.push(1);
    for(int i = 2; i <= nBuilding; ++i){
        while(!stk.empty() && height[stk.top()] >= height[i]){
            stk.pop();
        }
        if(!stk.empty()){
            dp[i] = max(height[i] - height[stk.top()], dp[stk.top()]);
        } else {
            dp[i] = 0;
        }
        stk.push(i);
    }
    sort(dp + 1, dp + nBuilding + 1);

    for(int q = 1; q <= Q; ++q){
        int energy;
        scanf("%d", &energy);
        int idx = upper_bound(dp + 1, dp + nBuilding + 1, energy) - dp - 1;
        cout << nBuilding - idx << "\n";
    }

    return 0;
}