Problem X: 【一维数组】子序列个数

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:108 Solved:39

Description

给定一串数列,求出所有递增和递减子序列的数目。
如:
7 2 6 9 8 3 5 2 1
可分成(7 2)(2 6 9)(9 8 3)(3 5)(5 2 1)5个子序列,结果就是5

Input

两行
第一行,n(n<100)
第二行,n个整数

Output

一个数

Sample Input Copy

9
7 2 6 9 8 3 5 2 1

Sample Output Copy

5