LPERMUT  Longest Permutation
You are given a sequence A of n integer numbers (1<=A_{i}<=n). A subsequence of A has the form A_{u}, A_{u+1} ... , A_{v} (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 A_{1}, A_{2}, ... ,A_{n} (1<=A_{i}<=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:
20210420 10:53:35
I think NlogN isn't a good choice. 

lotus_guy:
20150305 14:24:12
nice Last edit: 20170411 11:37:42 

JosÃ© Carlos GutiÃ©rrez:
20150224 22:22:19
my O(N*log^2 N) solution got AC 

crccw:
20140823 22:30:02
7


つ ◕_◕ ༽つ GIFF AC:
20140812 10:37:34
@Diptesh I believe subsequence in this problem means subsegment 

Diptesh Patel:
20140726 18:51:04
Answer for the given test should be 4, As we need to find subsequence. The longest permutation from the subsequence is 4_312. 

Hasan Jaddouh:
20130611 13:33:50
my solution completely wrong ,but got AC 

Ортур:
20120710 08:48:03
I got AC with nlogn without any optimisations. 

haoyifan:
20120322 01:26:57
thx,but,


Buda IM (retired):
20120312 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:  20060220 
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 