题目描述
给你一个包含n个整数的数列A1、A2、...、An，求其最长上升子序列的长度。
最长上升子序列指满足“从数列中依次选出一些整数，不改变先后顺序，且任意一对相邻的整数都满足前一个整数小于后一个整数”的条件下包含整数最多的那个（或那些）整数序列；最长上升子序列的长度即为其包含的整数个数。
输入
第一行包含一个整数n（1 ≤ n ≤ 1000）。
第二行包含n个整数，两两之间以一个空格分隔，依次表示A1、A2、...、An（1 ≤ Ai ≤ 1000）。
输出
一个整数，表示数列A的最长上升子序列的长度。
样例输入
3
1 2 3样例输出
3