LPERMUT - Longest Permutation

no tags 

You are given a sequence A of n integer numbers (1<=Ai<=n). A subsequence of A has the form Au, Au+1 ... , Av (1<=u<=v<=n). We are interested in subsequences that are permutations of 1, 2, .., k (k is the length of the subsequence).

Your task is to find the longest subsequence of this type.

Input

  • Line 1: n (1<=n<=100000)
  • Line 2: n numbers A1, A2, ... ,An (1<=Ai<=n)

Output

A single integer that is the length of the longest permutation

Example

Input:
5
4 1 3 1 2

Output:
3

hide comments
for_sx_e_1: 2021-04-20 10:53:35

I think NlogN isn't a good choice.

lotus_guy: 2015-03-05 14:24:12

nice

Last edit: 2017-04-11 11:37:42
José Carlos Gutiérrez: 2015-02-24 22:22:19

my O(N*log^2 N) solution got AC

crccw: 2014-08-23 22:30:02

7
6 5 1 3 3 3 3

anwsers 6 and got AC, Please review your tests

つ ◕_◕ ༽つ GIFF AC: 2014-08-12 10:37:34

@Diptesh I believe subsequence in this problem means subsegment

Diptesh Patel: 2014-07-26 18:51:04

Answer for the given test should be 4, As we need to find sub-sequence. The longest permutation from the sub-sequence is 4_312.

Hasan Jaddouh: 2013-06-11 13:33:50

my solution completely wrong ,but got AC

Ортур: 2012-07-10 08:48:03

I got AC with nlogn without any optimisations.

haoyifan: 2012-03-22 01:26:57

thx,but,
4
1 4 2 4
Why the answer is 2?

Buda IM (retired): 2012-03-12 06:14:10

Be ware this problem has VERY tight TL. You can AC with NlogN with many constant optimisations. I think O(N) is expected.


Added by:Jimmy
Date:2006-02-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:A problem put forward by Mr Mircea Pasoi