LPERMUT - Longest Permutation

题面翻译

题面：

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

输入输出：

Input 第一行，一个数 $n$，表示序列 $A$ 的长度 第二行，$n$ 个整数，第 $i$ 个数表示元素 $A_i$ Output 一个数，表示可选子集的长度

说明

你可以选的子集从 $A_3$ 开始到 $A_5$，这个子集长度为 $3$，包含了 $1,2,3$

$1\leq n\leq 100000,1 \leq A_i \leq n$

题目描述

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.

输入格式

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

输出格式

A single integer that is the length of the longest permutation

样例 #1

样例输入 #1

5
4 1 3 1 2

样例输出 #1

3