Cho một dãy số \(a_1,a_2,...,a_n(1\leq n\leq10^5)\), chúng ta cần tô màu các con số trên dãy, mỗi số đúng một màu thỏa mãn các số cùng màu ghép lại theo thứ tự sẽ được một dãy không tăng dần. Hỏi số màu ít nhất cần dùng.

INPUT

Dòng đầu chứa số nguyên \(n\).

Dòng thứ 2 chứa dãy \(a\) \((0\leq a_i\leq10^9)\).

OUTPUT

In ra số màu ít nhất.