ELIS - Easy Longest Increasing Subsequence

no tags 

Given a list of numbers A output the length of the longest increasing subsequence. An increasing subsequence is defined as a set {i0 , i1 , i2 , i3 , ... , ik} such that 0 <= i0 < i1 < i2 < i3 < ... < ik < N and A[ i0 ] < A[ i1 ] < A[ i2 ] < ... < A[ ik ]. A longest increasing subsequence is a subsequence with the maximum k (length).

i.e. in the list {33 , 11 , 22 , 44}

the subsequence {33 , 44} and {11} are increasing subsequences while {11 , 22 , 44} is the longest increasing subsequence.

Input

First line contain one number N (1 <= N <= 10) the length of the list A.

Second line contains N numbers (1 <= each number <= 20), the numbers in the list A separated by spaces.

 

Output

One line containing the lenght of the longest increasing subsequence in A.

 

Example

Input:
5
1 4 2 4 3
Output:
3

hide comments
hassanarif63: 2016-12-11 08:27:30

#Easy

shubh809: 2016-08-14 15:12:40

super easy with LIS

rayhan50001: 2016-04-23 19:57:42

Use LIS algorithm.....

rayhan50001: 2016-04-23 19:57:06

Easy one.. AC in First Go

zubayer_sust: 2016-03-13 20:38:48

got AC !!!

Junaid: 2015-12-14 19:10:16

my first DP...AC in one go...;)

karthik1997: 2015-10-01 17:57:29

DP rocks :p

Alex-ander007: 2015-09-18 01:22:50

AC in one go using dp ^_^

Changming: 2013-07-09 08:27:12

O(N^2) is enough. Because the length of the list A is very small.


Added by:Omar ElAzazy
Date:2012-03-17
Time limit:1.948s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64