In order for the ~i^{th}~ tree to be visible from either side, it must be taller than all the trees to the left or to the right of it.

Instead of looping to the beginning and to the end of the array for every tree, which would result in a ~O(N^2)~ runtime, we instead use a prefix maximum array and a suffix maximum array.

The prefix maximum array's ~i^{th}~ element is the tallest tree's height from the beginning of the array to ~i~, and the suffix maximum array stores the tallest tree's height from the end of the array to ~i~.

Both of these arrays should be precomputed, so that queries can be handled in constant time.

To output the solution for each ~i~, the amount that needs to be added to the ~i^{th}~ tree is:

min(pma[i-1], sma[i+1]) - trees[i] + 1

The minimum function finds the shortest tree that the ~i^{th}~ need to be taller than to be visible on one side. By subtracting the height of the ~i^{th}~ tree from that value, we find the amount to be added to the ~i^{th}~ tree for it to be as tall as one of the tallest trees on either side. Finally, by adding one, we make sure that it is visible from one side.

However, there's a case where the ~i^{th}~ tree is already visible from both sides, in which case the above formula will return a negative number. To solve for this case, simply find the maximum value between 0 and the above formula.

The final formula then is:

max(0, min(pma[i-1], sma[i+1]) - trees[i] + 1)