You are given an array $A$ of $n$ integers, find the longest increasing subsequence (LIS) of $A$.
In other words, find the largest $k$ that there exist $k$ indices $i_1 < i_2 < ... < i_k$ that $A_{i_1} < A_{i_2} < ... < A_{i_k}$.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integer $A_i$.
### Output
- Print the length of the LIS.
### Constraints
- $1 \le n \le 1000$
- $1 \le A_i \le 10^9$.
### Example
Input:
```
5
3 7 2 1 8
```
Output:
```
3
```
#### Note: The LIS is $(3, 7, 8)$.
