The large limit on ~N~ will make quadratic solutions time out.

To start with, suppose the heights of all people are distinct. Imagine going through the line in order. Observe any person ~A~ waiting in line. If, after person ~A~, we encounter a taller person ~B~, then person ~A~ surely can't see anyone after person ~B~.

Because of this, when going through the line, we can maintain a stack of "open subproblems", where an open subproblem is a person already encountered in the line, but who still has a possibility of seeing someone whom we haven't yet encountered. It should be obvious that the subproblems on the stack are sorted in descending order of height (topmost subproblem = shortest person).

When we encounter a new person, that person can see everyone on the stack that is shorter, and also takes those people off the stack (closing their subproblems). If the stack isn't empty after this, the person can also see the first person remaining on the stack. The person then enters the stack (there is a possibility that they will see someone later in line).

Even though the solution has two nested loops, the overall complexity is ~\mathcal O(N)~, because every person enters and leaves the stack exactly once, and each iteration of the inner loop pops one element off the stack.

To complete the solution, we need to consider the effect of persons equally tall. One way is to have the stack hold ordered pairs (height, number of people) and maintain it accordingly.