• Cho một dãy số nguyên a, hãy tìm độ lớn của dãy con tăng dài nhất của dãy này

Input

• Dòng đầu tiên chứa một số nguyên n, là độ lớn của dãy số (1 < n < ~10^6~)
• n dòng tiếp theo, mỗi dòng chứa một số nguyên của dãy a ( a < a[i] < ~10^5~)

Output

• Độ lớn của dãy con tăng dài nhất của a

Sample

Input #1

5
2
7
4
3
8

Output #1

3

Hint

• Với test trên, ta có thể nhận thấy dãy con tăng dài nhất là: [2,7,8] với độ lớn của dãy là 3