New City Planning

The height of each building can be chosen independently. Thus, the answer is the sum of $\max(B_1,\ldots,B_{A_i})$ over all buildings $i$.

For $h=2,3,\ldots,M$, update $B_h \gets \max(B_h,B_{h-1})$ in this order. Then stores the maximum of the first elements of the original array. The answer is .

The time complexity is $O(N+M)$ and the space complexity is $O(N+M)$.