Informatica Online Judge

  LZS3 [2380 / 094C]

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


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

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

Background

sjimed가 너무 빨리 새로운 LZS를 찾아낸 것에 놀라웠던 희승이는 과연 sjimed가 조건을 추가하더라도 sjimed식의 LZS의 길이를 빠르게 찾아낼 수 있을지 궁금하였다. 이에 희승이는 경기과학고의 신과 같은 존재 갓띵건에게 찾아가 어떻게 하면 좋을지 조언을 구하러 갔다. 이에 갓띵건은 아주 작은 조건을 추가하여 알려준 뒤 아직 다 못한 양방향 그래프에서의 다익스트라 알고리즘을 구현하러 갔다.(단방향은 이미 구현했다고 하더라.)(?)
어쨋든, 갓띵건이 조건을 추가하여 바꾼 LZS는 다음과 같다. 어떤 수열의 증가하는 부분수열 중 그 위치를 지그재그로 뽑는 대신, 왼쪽에서 뽑을 때 이전에 왼쪽에서 선택한 숫자보다 항상 오른쪽에 있는 숫자를 뽑는 것이다. 단 이 때 두 번째 숫자를 고를 때는 무조건 첫 번째 숫자의 오른쪽에 있는 숫자를 고르도록 한다. 예를 들어 8, 3, 1, 5, 2, 7의 수열이 있다고 생각하자. 이 때 LZS2는 1 - 2 - 3 - 5 - 8의 순서로 뽑으면 되었지만 LZS3에서는 1을 선택한 후 3을 선택할 수 없다. 따라서 이 경우 LZS3는 1 - 2 - 5 - 7 의 순서로 숫자를 뽑은 수열이 된다. 즉, LZS3의 길이는 4임을 알 수 있다. 과연 갓띵건이 추가한 조건 속에서도 sjimed는 빠르게 LZS의 길이를 구할 수 있을까? sjimed를 도와 그 길이를 구해보자.

Input

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

Output

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

IO Example

입력1
6
8 3 1 5 2 7

출력1
4

입력2
2
1 0

출력2
1

설명
첫 번째 입력의 경우 숫자를 1 2 5 7 의 순서로 고를 경우 LZS3가 된다. 이보다 길게 만들 순 없다.
두 번째 입력의 경우 LZS3의 두 번째 수는 무조건 첫 번째 수의 오른쪽의 수여야 하므로 0을 고른 후 1을 고를 수 없다.

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