【问题描述】
有一个长为n的正整数序列A，问它的最长交错子序列的长度是多少。
设序列A={a1,a2,...an}的长为r的一个子序列{ak1,ak2,...akr}，它是交错子序列当且仅当对于任意的i(1<i<r)，满足(aki>aki+1&&aki>aki-1)或(aki<aki+1&&aki<aki-1)。例如：1 3 1 3 1就是一个交替子序列，3 1 3 1 3也是。而1 2 3就不是一个交替子序列。
【输入】
输入第一行为一个正整数n，表示序列长度。
第二行为n个正整数，表示长为n的序列A的每一个值
【输出】
输出仅一行，一个整数，表示序列A的最长交错子序列长度
【输出输出样例1】
sequence.in
8
2 3 4 4 2 1 5 2
sequence.out
5

【样例1解释】
最长交错序列为：2 3 2 5 2，长度为5
【数据范围】
对于30%的数据，n<=20
对于60%的数据，n<=1000
对于100%的数据，n<=100000,1<=ai<=10^9