| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 131 | 74 | 67 | 59.821% |
길이 $N$의 수열 $A$가 주어진다. 이 수열의 부분 수열 중에서 인접한 두 원소의 차이가 정확히 $1$이 되지 않도록 하는 가장 긴 부분 수열의 길이를 구하여라.
첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 500\,000$)
둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 10^9$)
첫째 줄에 조건을 만족하는 부분 수열의 최대 길이를 출력한다.
2 1 2
1
5 1 2 2 1 1
3
7 10 13 11 12 10 13 11
5
어떤 수열의 부분 수열(subsequence)이란, 원래 수열에서 몇 개의 원소를 제거하여 얻을 수 있는 수열을 의미한다. 예를 들어, 수열 $[1, 3, 5]$의 부분 수열로 가능한 것은 $[]$, $[1]$, $[3]$, $[5]$, $[1, 3]$, $[3, 5]$, $[1, 5]$, $[1, 3, 5]$가 있다.