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

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

配列の部分列とは、元の順序を崩さずにいくつかの要素(0 個以上)を削除して得られるものを指します。たとえば、配列 a=[3,1,4,1,5,9,2,6,5]a = [3, 1, 4, 1, 5, 9, 2, 6, 5] において、[3,4,5,6][3, 4, 5, 6] は aa の部分列ですが、[3,1,1,2,5][3, 1, 1, 2, 5] は要素の順番が維持されていないため、この配列の部分列ではありません。

入力 (Input)

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

次の行には、配列の要素を表す a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤1091 \leq a_i \leq 10^9) が空白区切りで並びます。

出力 (Output)

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

Examples

Input

Output

8
1 3 2 4 5 2 6 5

5

6
10 9 2 5 3 7

3

Explanation

  1. 最初の例では、配列の最長増加部分列として [1,2,4,5,6][1, 2, 4, 5, 6] が得られます。

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

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB