(Giống bài LIQ) Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.

Input

• Dòng đầu tiên gồm số nguyên N.
• Dòng thứ hai gồm N số mô tả dãy.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán

Example

Input:
5
2 1 4 3 5

Output:
3