배고픈 소들

농부 존이 기르는 소 $N$마리($1 \le N \le 5{,}000$)는 각자 서로 다른 양의 정수 번호를 가지고 있으며, 이 번호는 모두 부호 있는 32비트 정수 범위 안에 들어간다. 존은 소들이 번호 순서대로 줄을 서서 먹이를 먹기를 바라지만, 소들은 좀처럼 협조하지 않는다.

존은 다음 규칙에 따라 소가 먹이를 먹도록 허락한다. 어떤 소는 자신이 가장 먼저 먹이를 먹도록 선택되었거나, 자신의 번호가 바로 직전에 먹이를 먹은 소의 번호보다 클 때에만 먹이를 먹을 수 있다. 먹이를 줄 소는 반드시 줄에 서 있는 순서(왼쪽에서 오른쪽)대로 골라야 하며, 중간의 소를 건너뛰는 것은 가능하다.

줄에 서 있는 소들의 번호 목록이 주어질 때, 존의 규칙에 따라 먹일 수 있는 소의 최대 마리 수를 구하여라.

예를 들어, 다음과 같이 11마리의 소가 줄을 서 있다고 하자.

2 5 18 3 4 7 10 9 11 8 15

이때 2, 3, 4, 7, 10, 11, 15 순서로 먹이면 총 7마리를 먹일 수 있으며, 이것이 가능한 최대 마리 수이다.

반면 2, 5, 3, 10, 15 순서로는 먹일 수 없다. 소 3의 번호가 바로 앞에서 먹은 소 5의 번호보다 크지 않기 때문이다.

• 첫째 줄: 정수 $N$이 주어진다.
• 둘째 줄부터: 줄에 서 있는 소들의 번호가 순서대로 공백으로 구분되어 주어진다. 마지막 줄을 제외한 각 줄에는 정수가 20개씩 들어 있으며, $N$이 20의 배수가 아니라면 마지막 줄에는 20개보다 적은 정수가 들어 있을 수 있다.

• 첫째 줄: 각 소의 번호가 바로 앞 소의 번호보다 큰, 가장 긴 소들의 사슬(부분 수열)의 길이를 출력한다.