Informatica Online Judge

  LZS1 [2370 / 0942]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 19   Total Tried : 20


The Champion of this Problem (C++) : gs18060 - ms / 323byte
My Best Submission (C++) : N/A

[36th 정희승(gs18103)]
Writer ID : [gs18103]

Background

LIS(Longest Increasing Subsequence)란 어떤 수열의 부분수열 중 가장 길이가 긴 수열을 말한다. 하지만 증가하기만 하는 수열에 따분함을 느낀 희승이는 수열의 값이 올라갔다 내려가는 것을 반복하는 수열에 재미를 느꼈다. 희승이는 이러한 수열 중 가장 긴 수열의 이름을 LZS(Longest Zigzag Subsequence)라고 명명하였다.

엄밀하게는 LZS란 어떤 수열의 부분수열 중 a(2i) > a(2i+1)이고 a(2i-1) < a(2i)이거나 a(2i) < a(2i+1)이고 a(2i-1) > a(2i)인 수열을 말한다. 임의의 수열이 주어졌을 때, 희승이는 매우 빠르게 LZS의 길이를 구하고 싶다. 희승이를 도와 가장 긴 LZS의 길이를 찾아주자.

Input

입력의 첫 줄에는 수열의 길이 n(1<=n<=100,000)이 주어진다. 두번째 줄에는 서로 다른 정수 n개가 차례로 입력된다. i번째 들어오는 수 a_i는 수열의 i번째 수를 의미한다.(0<=a_i<=1,000,000,000)

Output

첫 줄에 LZS의 길이를 출력한다.

IO Example

입력
6
1 3 7 2 6 10

출력
4

설명
1 7 2 6을 고를 경우 LZS가 된다. 이보다 길게 만들 순 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]