오름세

주식 투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다.

정인이는 $n$일 동안 매일 주가를 적어 두었고, 여기에서 오름세를 찾아보려고 한다.

$n$일 동안의 주가를 $p_1, p_2, \ldots, p_n$이라고 하자. 오름세란 인덱스가 $i_1 < i_2 < \cdots < i_k$이면서 $p_{i_1} < p_{i_2} < \cdots < p_{i_k}$를 만족하는 부분수열, 즉 주가의 강한 증가 부분수열을 말한다.

$n$일 동안의 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 입력의 끝까지 처리한다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 $N$이 주어진다($N \le 100000$). 둘째 줄에는 관찰한 주가가 첫날부터 순서대로 주어진다. 주가는 한 개 이상의 공백으로 구분되며, 그 외의 위치에서도 공백이 자유롭게 나올 수 있다. 각 주가는 100{,}000보다 작거나 같은 자연수이다.

각 테스트 케이스에 대해, 입력으로 주어진 주가에서 가장 긴 오름세의 길이를 출력한다.