原题：
小Z最擅长解决序列问题啦，什么最长公共上升然后下降然后上升的子序列，小Z都是轻松解决的呢。
但是小Z不擅长出序列问题啊，所以它给了你一道签到题。
给定一个n个数的序列ai，你要求出满足下述条件的点对的数量。
假设点对是(i , j)，max(l,r)是[l,r]当中最大的ai的值。
这个点对满足条件当且仅当i+1<j 且 ai < max(i+1,j-1) < aj
为了简单，保证输入的是一个1-n的排列。相信你已经会做了吧？
输入/输出格式
输入数据第一行有一个数字n，然后第二行有n个数。
输出仅包含一个数，表示满足条件的数对的数量。
样例输入/输出
Input:
5
1 2 3 4 5
Output:
6
样例解释
满足条件的分别是(1,3),(1,4),(1,5),(2,4),(2,5),(3,5)
数据范围与约定
对于50%的数据，满足n<=300
对于95%的数据，满足n<=10000
对于100%的数据，满足n<=1000000
好吧，我承认。
这次考试所有的数据结构我都没学。（蒟蒻瑟瑟发抖。。）
首先看到题目n<=1000000
所以要O（N）算法
然而不论是线段树还是其他的算法维护max都是O(nlogn)(TLE 95分)
所以。。。
我们需要新的数据结构！
学长说这道题，水的很。。
单调栈来一个就搞过了。。（没学过。。。）
然后赶紧大补特补。。
单调栈就像一个简化版本的单调队列。
不过head是1，且队头指针永远不变
很显然，如果我们从n往1搜,a[i]对题目有贡献当且仅当a[i]右侧有2个比a[i]大的数
而它对答案的贡献就是右侧比它-2（点对条件看题目。。）
所以。。
就很简单啦。。（虽然我根本在考场上没写出来。。）
下面普及一下单调队列和单调栈的实现
首先我们先了解一下单调队列以及单调栈的操作
1、将一个元素插入队列。
2、将比这个元素大或等于这个元素的元素踢出队列
1的代码实现：que[++tail]=a[i];
2的代码实现：while(head<=tail&&que[tail]>=a[i])tail--;
当然有的题目还需要将队头向前移动：while(条件)head++;
然后我们将2个操作结合，就是单调队列啦、
在查询的时候我们只需要输出que[head]即可。（如果是单调栈，则输出que[1]）;
由于每一个元素都进队一次，出队一次
复杂度均摊O(N)查询O(1);
所以很快QAQ
那为什么我们要用单调栈呢？
这个，，自己理解题意。。维护区间最小值、、
为什么要从N往1搜呢？（搞了好久才懂）
因为这道题求得是区间MAX，所以若从1往n搜，我们只能维护区间最小值，而队列中的元素会被后来的元素挤掉（无法统计答案），因为单调队列无法插入，只能用tail指针删除。所以要从N到1啦QAQ
Orz zxyer(1小时AK)
下面贴代码
#include<iostream> #include<cstdio> using namespace std; int t,n; unsigned long long ans; int a[1000001]; int que[1000001]; int main(){ freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=n;i>=1;i--) { while((t)&&(que[t]<a[i])){t--;} que[++t]=a[i]; if(t-2>0) ans+=t-2ll; } printf("%lld ",ans); fclose(stdin); fclose(stdout); }