UChicago Practice Contest 2018-04-28

Start

2018-04-28 17:00 UTC

UChicago Practice Contest 2018-04-28

End

2018-04-28 22:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -386 days 1:41:10

Time elapsed

5:00:00

Time remaining

0:00:00

Problem K
Zigzag

A sequence of integers is said to Zigzag if adjacent elements alternate between strictly increasing and strictly decreasing. Note that the sequence may start by either increasing or decreasing. Given a sequence of integers, determine the length of the longest subsequence that Zigzags. For example, consider this sequence:

1 2 3 4 2

There are several Zigzagging subsequences of length $3$:

1 3 2        1 4 2        2 3 2        2 4 2        3 4 2

But there are none of length greater than $3$, so the answer is $3$.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains an integer $n$ ($1 \le n \le 1\, 000\, 000$) which is the number of integers in the list. Each of the following $n$ lines will have an integer $k$ ($1 \le k \le 1\, 000\, 000$).

Output

Output a single integer, which is the length of the longest Zigzagging subsequence of the input list.

Sample Input 1 Sample Output 1
5
1
2
3
4
2
3
Sample Input 2 Sample Output 2
6
1
1
1
1
1
1
1