#P1318. [Spoj744] Longest Permutation

    ID: 330 传统题 1000ms 512MiB 尝试: 684 已通过: 311 难度: 6 上传者: 标签>CF2100提高分治算法滑动窗口前后缀最值固定一个变量消去另一维

[Spoj744] Longest Permutation

题目描述

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

输入格式

第一行,一个数 nn,表示序列 AA的长度 第二行,nn 个数,第 ii 个数表示元素 AiA_i

输出格式

一个数,表示可选子集的长度

5
4 1 2 3 2
4

提示

你可以选得子集从 A1A_1 开始到 A_4$ ,这个子集长度为4,包含了1,2,3,4)

1≤n≤1000101\leq n\leq 100010