시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 37 32 9 90.000%

문제

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.

입력

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 ≤ n ≤ 1,000,000) which is the number of integers in the list. Each of the following n lines will have an integer k (1 ≤ k ≤ 1,000,000)

출력

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

예제 입력

5
1
2
3
4
2

예제 출력

3

예제 입력 2

6
1
1
1
1
1
1

예제 출력 2

1

힌트