题目描述

给定一个长度为 $n$ 的整数序列：

请你从中选出若干个数，要求：

1. 选出的数在原序列中的相对顺序不变；
2. 选出的数严格递增。

请你求出能够选出的最长长度。

也就是说，请你求这个序列的最长上升子序列长度。

本题中 $n$ 较小，请使用搜索思想解决。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数：

输出格式

输出一个整数，表示最长上升子序列的长度。

输入输出样例 #1

输入 #1

6
1 5 2 3 4 0

输出 #1

4

输入输出样例 #2

输入 #2

5
5 4 3 2 1

输出 #2

1

说明/提示

样例 $1$ 中，可以选择：

1 2 3 4

长度为 $4$。

样例 $2$ 中，原序列严格递减，因此最长上升子序列长度为 $1$。

数据范围

对于 $100\%$ 的数据：