| 问题描述 |
|---|
定义锯齿子序列：某序列中的一个非空子序列，且该子序列中首尾以外的元素$$a_i$$都满足： 若$$a_i > a_{i-1}$$，那么$$a_i > a_{i+1}$$； 若$$a_i < a_{i-1}$$，那么$$a_i < a_{i+1}$$。 例如$$1,5,2,6$$是锯齿子序列，但$$1,3,5$$不是锯齿子序列。 现在给出一个长度为$$n$$的序列，请你求出该序列的最长锯齿子序列的长度。
|
| 输入描述 |
第一行是一个正整数$$n$$表示序列的长度。($$1 \le n \le 10^3$$) 接下来一行$$n$$个互不相同的正整数$$a_i$$表示序列的每个元素。($$1 \le a_i \le 10^5$$)
|
| 输出描述 |
在一行中输出给定序列的最长锯齿子序列的长度。 |
| 样例输入复制样例 |
6 1 3 5 2 4 6 |
| 样例输出 |
4 |
| 相关 |