记录编号	165166	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]花匠	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2015-06-10 16:21:28	内存使用	5.63 MiB

//AUTHOR::STDAFX
//ALGORITHM::

#define MAX(a,b) ((a)>(b)?(a):(b))

#define MAXN 200010

#include <cstdio>

using namespace std;

struct Deq{
    int data[MAXN],tail,head,id[MAXN];
    inline void clr(){
        tail=-1;
        head=0;
        return;
    }
    inline bool empty(){
        return tail<head;
    }
    inline void pop_front(){
        if(!empty()){
            head++;
        }
        return;
    }
    inline void push_back(int temp,int new_id){
        data[++tail]=temp;
        id[tail]=new_id;
        return;
    }
    inline void pop_back(){
        tail--;
        return;
    }
    inline int front(){
        return data[head];
    }
    inline int front_id(){
        return id[head];
    }  
    inline int back(){
        return data[tail];
    }
    //单调上升 
    inline int push_up(int temp,int new_id){
        while(!empty()&&back()>=temp){
            pop_back();
        }
        if(empty()){
        	push_back(temp,new_id);
        	return 0L;
		}
        int rtn=id[tail];
        push_back(temp,new_id);
        return rtn;
    }
    //单调下降 
    inline int push_down(int temp,int new_id){
        while(!empty()&&back()<=temp){
            pop_back();
        }
        if(empty()){
        	push_back(temp,new_id);
        	return 0L;
		}
        int rtn=id[tail];
        push_back(temp,new_id);
        return rtn;
    }
};

Deq deq_max,deq_min;

inline int in();

int n,up[MAXN],down[MAXN],data[MAXN];

int main(){
	freopen("FlowerNOIP2013.in","r",stdin);
	freopen("FlowerNOIP2013.out","w",stdout);
	n=in();
	for(int i=1;i<=n;i++){
		data[i]=in();
	}
	deq_max.push_back(data[1],1);
	deq_min.push_back(data[1],1);
	up[1]=down[1]=1;
	for(int i=2;i<=n;i++){
		int pos_up=deq_max.push_down(data[i],i);
		int pos_down=deq_min.push_up(data[i],i);
		//printf("%d %d %d %d\n",i,data[i],pos_up,pos_down);
		up[i]=MAX(down[pos_down]+1,up[i-1]);
		down[i]=MAX(up[pos_up]+1,down[i-1]);
		//printf("%d %d\n",up[i],down[i]);
	}
	printf("%d",MAX(up[n],down[n]));
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

inline int in(){
	int temp=0;bool flag=0;char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') flag=1;
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()){
		temp=temp*10+c-48;
	}
	if(flag) return -temp;
	return temp;
}