【题目描述：】

N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。

写一个程序计算出有多少对人可以互相看见。

【输入格式：】

输入的第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍*有N个人。

接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10的-9次方米)为单位，每个人的调度都小于2^31毫微米。这些高度分别表示队伍中人的身高。

【输出格式：】

输出仅有一行，包含一个数S，表示队伍*有S对人可以互相看见。

【样例：】

输入样例#1： 7

            2 4 1 2 2 5 1

输出样例#1： 10

[算法分析：]

暴力枚举的话\(O(n^3)\)的复杂度肯定会超时，500000的数据\(n^2\)也会死的很惨，考虑\(O(nlog_2n)\)或者是\(O(n)\)的算法.

使用单调栈：

每当有一个元素a读入时，将其与栈顶元素比较，如果大于等于栈顶元素，就把栈顶pop()掉，累加答案，继续比较

一直pop到栈顶元素小于a时，如果栈里面还有元素，答案+1

之后把a push进栈里，并把之前等于a但被pop掉的元素加入。

时间复杂度还是比较好的，对于这道题来说绰绰有余..

一些数据比如像“500000 1 1 1 1 1 ... 1”之类的会被卡，不过这道题数据弱..不必特判

但是。。还有一道双倍经验题，题目一模一样的，数据范围也一样，但是数据加强了，要开long long，，而且这种方法会T掉五个点..

（不特判全等数据会T掉六个点...）

（不开long long加特判的话只会T三个点，但是还有一个点爆int了所以有四个点过不了）

点这里，没错就是这道题！

所以说还需要进一步地优化这种算法。




\([Code:]\)

//没有优化的laji单调栈

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN = 500000 + 1;

int n;

int a[MAXN];

deque<int> q;

inline int read() {

    int x=0, f=1; char ch=getchar();

    while(ch<'0' || ch>'9') {

        if(ch == '-') f = -1;

        ch = getchar();

    }

    while(ch>='0' && ch<='9')

        x=(x<<3)+(x<<1)+ch-48, ch=getchar();

    return x * f;

}

int main() {

    n = read();

    int ans = 0;

    for(int i=1; i<=n; ++i) a[i] = read();

    for(int i=1; i<=n; ++i) {

        int t = 0;

        while(!q.empty() && q.back()<=a[i]) {

            if(q.back() == a[i]) ++t;

            q.pop_back();

            ++ans;

        }

        if(!q.empty()) ++ans;

        q.push_back(a[i]);

        while(t--) q.push_back(a[i]);

    }

    printf("%d\n", ans);

}