Longest Increasing Subsequence (最長増加部分列) 1

与えられたのは、n 個の整数からなる配列です。この配列に対して、最長の増加部分列を見つけることが求められています。もし同じ長さの最長増加部分列が複数存在するなら、そのうちどれを出力しても構いません。

配列の部分列とは、元の順序を崩さずにいくつかの要素（0 個以上）を削除して得られるものを指します。たとえば、配列 において、 は の部分列ですが、 は要素の順番が維持されていないため、この配列の部分列ではありません。

入力 (Input)

最初の行には、配列の長さを表す整数 n (1 ≤ n ≤ 1000) が与えられます。

次の行には、配列の要素を表す () が空白区切りで並びます。

出力 (Output)

配列の最長増加部分列の長さを出力してください。

Examples

Explanation

1. 最初の例では、配列の最長増加部分列として が得られます。

2. 二番目の例では、最長増加部分列として が得られます。