LPIS - Longest Perfect Increasing Subsequence


Dhrubo has a sequence of N integers. He is trying to find the longest perfect increasing subsequence of that sequence. But he is not very expert in finding longest perfect increasing subsequences. So he needs your help.

A subsequence is a sequence that can be derived by another sequence by deleting elements without changing the order of the remaining elements. An increasing subsequence of a sequence is a subsequence where the elements are sorted in increasing order.

Difference between an increasing subsequence and a perfect increasing subsequence is that in a perfect increasing subsequence the difference between any two consecutive elements is always 1.

For example, let’s consider a sequence S= {5, 2, 6, 3, 7, 8, 4}

{5, 3, 4} is subsequence of sequence S but not an increasing subsequence.

{5, 7, 8} is an increasing subsequence of sequence S, but not a perfect increasing subsequence.

But {5, 6, 7, 8} is perfect increasing subsequence as the difference between any two consecutive elements is exactly 1.

Note that, a single element will always be perfect increasing subsequence. So {5}, {2}, {7} are also perfect increasing subsequence of S.

Input

First line of the input contains an integer N (1 <= N <= 105) denoting the length of the sequence.

Next line contains N integers separated by space which is the sequence. These integers will be greater than 0 and will not be greater than 106.

Output

A single integer in a line denoting the length of the longest perfect increasing subsequence.

Example

Input #1:
9
5 1 5 6 2 3 8 7 4

Output #1:
4
Input #2:
8
2 2 1 3 5 4 5 6

Output #2:
5

(set by : Nashir Ahmed)


hide comments
mahakaal2018: 2018-12-10 16:25:33

Must Solve!!!

hello_world123: 2018-07-17 08:40:14

Simple but tricky!!!

realife_playa: 2017-10-20 19:35:06

Could someone please post a link for the solution. I am unable to get it even after several hours of trying.

k_nushka: 2017-07-06 20:38:43

O(N) with simple trick. :)

heisenberg0820: 2017-06-22 21:31:55

A must try on Spoj :)
O(n) soln possible

omprakash_40: 2017-03-23 07:17:14

nice..problem..
AC in on go..just keep in mind that arr[i]<=10^6...O(n) solution.

flyingduchman_: 2016-10-25 14:47:46

STL :unordered_map<int,int> or int array[1000000];
piece of cake !

Last edit: 2016-10-25 15:15:16
vaibhav138: 2016-07-21 01:38:51

Nice question
For O(n) try to use the fact that a[i] <= 10^6

akshayvenkat: 2016-07-20 18:29:17

yaay AC in one go :D ad hoc'ed DP :D

azam_9: 2016-02-18 08:42:14

got AC..credit goes to @dungeon_master.....:D


Added by:Md. Najim Ahmed
Date:2015-12-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY