#3311. LPERMUT - Longest Permutation

LPERMUT - Longest Permutation

LPERMUT - Longest Permutation

题面翻译

题面:

给你一个序列 AA 含有 nn 个正整数 (1Ain)(1\leq A_i\leq n)AA 的子集形式类如 Au,Au+1,,Av(1uvn)A_u,A_{u+1} , \dots , A_v (1\leq u\leq v\leq n),即必须是连续的。我们感兴趣的是一种子集,它含有元素包括 1,2,,k1,2,\dots,k。(kk 是子集的大小)。 你的任务是找到这种类型的最长的子集。

输入输出:

Input 第一行,一个数 nn,表示序列 AA 的长度 第二行,nn 个整数,第 ii 个数表示元素 AiA_i Output 一个数,表示可选子集的长度

说明

你可以选的子集从 A3A_3 开始到 A5A_5,这个子集长度为 33,包含了 1,2,31,2,3

1n100000,1Ain1\leq n\leq 100000,1 \leq A_i \leq n

题目描述

You are given a sequence A of n integer numbers (1<=A i _{i} <=n). A subsequence of A has the form A u _{u} , A u+1 _{u+1} ... , A v _{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.

输入格式

  • Line 1: n (1<=n<=100000)
  • Line 2: n numbers A 1 _{1} , A 2 _{2} , ... ,A n _{n} (1<=A i _{i} <=n)

输出格式

A single integer that is the length of the longest permutation

样例 #1

样例输入 #1

5
4 1 3 1 2

样例输出 #1

3