/ Vijos / 题库 /

丰盛的晚宴

丰盛的晚宴

背景

Fz是个美食家,他经常自己烹饪一些美味佳肴来供自己的客人享用。

这天,Fz又有了一批重要的客人:机房的全体同仁。于是他决定烹饪一餐无与伦比的美味。但是,当Fz看到自家的冰箱时,不禁皱了眉头——空的。于是Fz不得不赶快到菜市场准备原料去了。

菜市场的n个店铺分布在一条直线上,每个店铺只供应一种原料,我们将这些原料从1至m标号。Fz可以做m种宴席,第k种宴席恰好需要前k种原料,并且对于这种大厨来说,用得原料越多显然就越好。但是Fz现在既希望能够做一餐最好的晚餐,也希望能够花尽量少的时间,所以他规定:
1) 自己可以从任意一个店铺进入菜市场;
2) 自己每次可以从一个店铺移动到一个相邻的店铺;
3) 自己不会经过两个卖同样原料的店铺;
4)自己经过的店铺所供应的原料刚好能够做一顿宴席不会有多。

描述

给定一个长度为n的整数序列,元素定义域为[1 .. n],求其中一个最长的连续子序列S,使得其恰好为一个1至|S|的排列。

格式

输入格式

第一行有一个数T,表示数据组数,对于每组数据:
接下来T组数据:
第一行一个整数n,表示菜市场长度;
第二行n个数,表示对菜市场的描述;

对于50%的数据,有:
1 <= n <= 1000,1 <= T <= 100;
对于另外50%的数据,有:
1 <= n <= 2 * 105;1 <= T <= 10;

输出格式

每组数据只有一行,两个数p、q,表示|S| = p,且|S|的最早可能的起始位置为q(无解时q = 0)

样例1

样例输入1

6
4
4 3 2 1 
4
2 1 2 3 
4
3 3 2 1 
4
2 1 1 3 
4
3 2 4 1 
4
2 1 4 2

样例输出1

4 1
3 2
3 2
2 1
4 1
2 1

限制

每个测试点1秒.

信息

ID
1381
难度
7
分类
其他 | 数学 点击显示
标签
(无)
递交数
132
已通过
22
通过率
17%
上传者

相关

在下列训练计划中:

RP++分类题库