题目描述

给你一个长度为 $n$ 的序列，请找到他的一个最长的上升且奇偶交替的子序列。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数 $a_1\sim a_n$，即给你的序列。

输出格式

一行一个整数，表示最长上升奇偶子序列的长度。

10
1 4 5 8 6 11 9 20 10 13 

7

样例解释

一种方案是 $\{1,4,5,6,9,10,13\}$

数据规模与约定

对于 $100\%$ 的数据，$1\le n \le 5000$、$1\le a_i\le 10^9$。

• 子任务 1（30 分）：保证原序列就是个上升子序列。
• 子任务 2（70 分）：没有特殊限制。