Informatica Online Judge

  LZS2 [2379 / 094B]

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


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

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

Background

희승이의 LZS 이야기를 들은 sjimed는 그 이름을 듣고 조금 다르게 생각했다. 바로 수열에서 증가하는 수열을 지그재그로 뽑는 것이다! 예를 들어 1 3 7 2 6 10의 수열이 있다고 생각하자. 그 때 1 - 2 - 3 - 6 - 7 - 10의 순서로 숫자를 선택하게 되면 그 수열은 증가하는 수열이지만 원래 수열에서 어떤 숫자를 뽑는 위치는 진동한다. sjimed는 이러한 수열 중 가장 긴 수열을 LZS2로 명명하였다. 하지만 너무나 똑똑한 나머지 sjimed는 이 수열을 생각하고 몇 초 뒤에 바로 LZS2의 길이를 빠르게 구하는 방법을 알아냈다. 과연 sjimed는 어떻게 했을까?

Input

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

Output

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

IO Example

입력
6
8 3 1 5 2 7

출력
5

설명
숫자를 1 2 3 5 8 의 순서로 고를 경우 LZS2가 된다. 이보다 길게 만들 순 없다.

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