Competitions

# Five for week 15

# Subsequence

Given a sequence, find the length of the largest strictly increasing subsequence.

## Input data

First line contains the length n (1 ≤ n ≤ 1000) of the sequence. The second line contains the sequence itself. All numbers are integers not exceeding 10000 by absolute value.

## Output data

Print the maximum length of strictly increasing subsequence.

## Examples

Input example #1

6 3 29 5 5 28 6

Output example #1

3