记录编号	165167	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]花匠	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2015-06-10 16:56:36	内存使用	2.20 MiB

#include<cstdio>
#define MAX(a,b) (a)>(b)?(a):(b)

using namespace std;

int n,a[100100],q1[100100],q2[100100],up[100100],down[100100];
int tail1=0,tail2=0,head1=1,head2=1;

void push(int i)
{
	while(head1<=tail1&&a[q1[tail1]]<=a[i])
	{
		tail1--;
	}
	q1[++tail1]=i;
	while(head2<=tail2&&a[q2[tail2]]>=a[i])
	{
		tail2--;
	}
	q2[++tail2]=i;
	
}

int main()
{
	freopen("FlowerNOIP2013.in","r",stdin);
	freopen("FlowerNOIP2013.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	up[1]=down[1]=1;
	push(1);
	for(int i=2;i<=n;i++)
	{
		push(i);
		int j=q1[tail1-1];
		up[i]=MAX(down[j]+1,up[i-1]);
		j=q2[tail2-1];
		down[i]=MAX(up[j]+1,down[i-1]);
	}
	printf("%d",MAX(up[n],down[n]));
}