Description

给定一个整数序列$A_1;A_2;A_3;…;A_n$。求它的一个递增子序列，使子序列的元素个数尽量多，元素不一定要求连续。

Format

Input

第1行：1个整数n($1\leq n \leq 5000$)，表示序列中元素的个数.

第2行：每行1个整数x$(-1000 \leq x\leq 1000)$，表示序列中的第i个元素。

Output

第1行：1个整数k，表示最长上升子序列的长度。

Samples

11
2 3 3 4 5 1 4 6 2 7 4

6

Limitation

1s, 1024KiB for each test case.