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 Asurely can't see anyone after person B.
观察队伍中的一个人A。如果我们他后面找到了一个比他不知道高到哪里去了的B，A就不能与B后面的人谈笑风生了。
Because of this, when going through the line, we can maintain a stack of "open subproblems", wherean open subproblem is a person already encountered in the line, but who still has a possibility of seeingsomeone whom we haven't yet encountered. It should be obvious that the subproblems on the stackare 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 alsotakes those people off the stack (closing their subproblems). If the stack isn't empty after this, theperson can also see the first person remaining on the stack. The person then enters the stack (there is apossibility that they will see someone later in line).
当我们找到一个新的高人时，他可以向栈里比他naive人的传授人生经验，并让他们出栈。如果出栈之后栈非空，他还可以与栈顶的高人谈笑风生。然后我们再另请这位高明进栈。
Even though the solution has two nested loops, the overall complexity is O(N), because every personenters and leaves the stack exactly once, and each iteration of the inner loop pops oneelement off thestack.
有人问了一个simple的问题：这样的解法不是有两层循环吗？然而它的总复杂度是$O(N)$，因为每个人的进栈与出栈都只有一次，内层的每次循环从栈中弹出一个高人。
To complete the solution, we need to consider the effect of persons equally tall. One way is to have thestack hold ordered pairs (height, number of people) and maintain it accordingly.
要A掉这道题我们还要考虑两个人身高相同的情况。我们可以在栈里存pair<身高，人数>并维护它。
官方标程：
```
/*
Croatian Olympiad in Informatics 2007
Task PATRIK
*/
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;
typedef long long llint;
typedef pair<int,int> par;
stack<par> S;
int main( void ) {
int n;
scanf( "%d", &n );
llint ret = 0;
for( int i = 0; i < n; ++i ) {
int h;
scanf( "%d", &h );
par p( h, 1 );
for( ; !S.empty() && S.top().first <= h; S.pop() ) {
ret += S.top().second;
if( S.top().first == h ) p.second += S.top().second;
}
if( !S.empty() ) ++ret;
S.push( p );
}
cout << ret << endl;
return 0;
}
```