문제

길이가 $N$인 수열 $a_1, a_2, \cdots, a_N$이 주어질 때, 이 수열의 부분 수열 $b_1, b_2, \cdots, b_M(1 \le M \le N)$이 도미노 수열이 되려면 다음과 같은 조건을 만족해야 한다.

주어진 수열의 부분 수열 중 도미노 수열의 최대 길이를 구해보자.

입력

첫째 줄에 정수 $N(1 \le N \le 200\,000)$이 주어진다.

둘째 줄에 정수 $a_1, a_2, \cdots, a_N(1 \le a_i \le 10^9)$이 공백으로 구분되어 주어진다.

출력

주어진 수열의 부분 수열 중 도미노 수열의 최대 길이를 출력한다.

예제 입력 1

6
2 3 1 9 4 3

예제 출력 1

4

부분 수열 중 $\{a_2,a_3,a_5,a_6\} =\{3,1,4,3\}$이 가장 긴 도미노 수열이다.

예제 입력 2

5
2 1 5 4 3

예제 출력 2

3

부분 수열 중 $\{a_1,a_2,a_5\} =\{2,1,3\}$이나 $\{a_3,a_4,a_5\} =\{5,4,3\}$이 가장 긴 도미노 수열이다.

예제 입력 3

7
3 1 7 4 11 12 13

예제 출력 3

5

부분 수열 중 $\{a_3,a_4,a_5,a_6,a_7\} =\{7,4,11,12,13\}$이 가장 긴 도미노 수열이다.

예제 입력 4

4
3 1 2 6

예제 출력 4

4

예제 입력 5

3
1 2 3

예제 출력 5

1

노트

부분 수열이란 주어진 수열에서 $1$개 이상의 원소를 골라 원래 순서대로 나열한 수열이다.