Expert.
Put your skills to the test.

Problem summary

N buildings stand in west-to-east order with distinct heights. A tower may be placed in any gap, including either end, and broadcasts only westwards. A building receives the signal exactly when it is west of the tower, lower than the tower, and no intervening building is taller than it. For each proposed tower height, find the maximum number of receiving buildings over all placements.

Constraints

1 ≤ N ≤ 1,000,000; 1 ≤ K ≤ 100,000; heights are integers from 1 to 10^9. Building heights are distinct; proposed heights are distinct and differ from every building height.

Worked example

Official sample. Height 180 can receive six buildings when placed after building 8.

16 3
200 170 155 90 150 140 40 30 185 160 50 110 80 15 70 35
165 180 120

5 6 4

Solution analysis

1. For a fixed gap, scan buildings to its left from right to left. A building is visible only if it is higher than every building already encountered. These visible heights form a strictly decreasing stack when stored from west to east. Buildings below the tower form a suffix of this stack.
2. Scan the street once using a decreasing monotonic stack. Before pushing building v, pop lower buildings. The remaining top is parent[v], the nearest earlier taller building. Each stack version is now a root-to-node path in this implicit parent tree. Although popped buildings disappear from the current version, their parent links preserve earlier versions.
3. Let best[v] be the largest number of vertices in a downward path beginning at v in this parent tree. Since parents always have smaller indices, process buildings backwards and set best[parent[v]] = max(best[parent[v]], best[v]+1). No recursive traversal or explicit child lists are required.
4. A downward path beginning at v represents a suffix of a visible stack at some gap. All its heights are at most height[v], so a tower H can receive that entire path if height[v] < H. Sort buildings by height, form prefix maxima of best, and answer each tower by binary search. For heights 20,10,15,8,17, a tower of height 16 sees 8 and 15 after the fourth building, while height 21 can additionally see 20: the answers are 2 and 3.

Why it works

The monotonic stack removes exactly the buildings obscured by the newly read taller building, so each prefix stack contains exactly its westward visible records. Parent links reconstruct every such stack path. A receiving suffix starts at a building lower than H; its maximum possible length is best[v]. Conversely each downward path is present in the stack after its final building is read. Maximizing best over heights below H therefore considers exactly all feasible receiving sets.

Watch out. Do not count every lower building: intervening taller buildings block it. The signal points west only. A recursive tree DFS may overflow the call stack for a million buildings; reverse index order avoids this. Do not sort the street before constructing parents.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int>height(n+1),parent(n+1),best(n+1,1),stack;
    for(int v=1;v<=n;v++){
        cin>>height[v];
        while(!stack.empty()&&height[stack.back()]<height[v]){
            stack.pop_back();
        }
        parent[v]=stack.empty()?0:stack.back();
        stack.push_back(v);
    }
    // Every child has a larger index, so its value is ready first.
    for(int v=n;v>=1;v--){
        if(parent[v]!=0){
            best[parent[v]]=max(best[parent[v]],best[v]+1);
        }
    }
    vector<pair<int,int>>ordered;
    ordered.reserve(n);
    for(int v=1;v<=n;v++){
        ordered.push_back({height[v],best[v]});
    }
    sort(ordered.begin(),ordered.end());
    vector<int>heights(n),prefixBest(n);
    for(int i=0;i<n;i++){
        heights[i]=ordered[i].first;
        prefixBest[i]=max(i==0?0:prefixBest[i-1],ordered[i].second);
    }
    for(int i=0;i<k;i++){
        int tower;
        cin>>tower;
        int count=lower_bound(heights.begin(),heights.end(),tower)-heights.begin();
        cout<<(count==0?0:prefixBest[count-1])<<(i+1==k?'\n':' ');
    }
}