There are multiple strategies to pop the balloons in this task. We will mention only the one implemented in the official solution.

The optimal strategy is the following: pick the first balloon from the left that isn't still popped and shoot an arrow in its height. Let's try and prove the validity of this algorithm.

The leftmost balloon must be hit by an arrow in a way that at least one arrow begins at its spot. The only question is whether it is sometimes better to first pop a higher balloon to the right and only then this one.

Let's notice two cases:

1. In the case when the set of balloons that would be popped by shooting an arrow into that higher balloon and the first balloon don't intersect, it is clearly not important which one of the two we pop first.
2. In the case when these two sets intersect, let's notice that this intersection is a suffix of these two sets. In other words, if an intersection exists, it is made out of several rightmost elements, which means that is also irrelevant which one we pop first.

The described algorithm can be implemented using the STL structure called set. The question which the set is going to answer is "What is the first balloon that hasn't been popped yet, is in the height ~H-1~ and is located to the right of the current position ~P~?"

We need to have ~H~ sets, one per height from ~1~ to ~H~. The ~H^\text{th}~ set will store the positions where the balloons at height ~H~ appear at.

With simple queries to the set and popping the elements from the set, it is still possible to maintain the structure that answers the required question.

The time complexity of this algorithm is ~\mathcal O(N \log N)~, the memory complexity ~\mathcal O(N)~. The solution of complexity ~\mathcal O(N)~ is also possible for this task and we leave this as a practice to the reader. (Hint: try to shoot all the arrows at the same time.)