#P14131. 【MX-X22-T2】「TPOI-4B」K Problem

    ID: 15839 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>贪心O2优化哈希 hashing双指针 two-pointer梦熊比赛

【MX-X22-T2】「TPOI-4B」K Problem

题目描述

给定长度为 nn 的正整数序列 a1,,ana_1, \ldots, a_n

你要找到一个最大的正整数 kk,满足序列 aa 中存在一个区间仅含有数字 1k1 \sim k 且含有恰好 1111,恰好 2222,恰好 3333\dots,恰好 kkkk。若不存在这样的 kk,则输出 00

输入格式

本题输入包含多组数据。

第一行,一个整数 TT,表示数据组数。对于每组数据:

  • 第一行,一个正整数 nn
  • 第二行,nn 个正整数 a1,,ana_1, \ldots, a_n

输出格式

对于每组测试数据:

  • 一行,一个非负整数,表示你的答案,即最大的正整数 kk,或输出 00 表示这样的 kk 不存在。
3
6
1 2 1 2 1 2
8
1 2 3 3 2 1 3 2
6
2 3 3 2 3 3
2
3
0

提示

【样例解释】

该样例共有 33 组测试数据。

对于第一组数据,当 k=2k = 2 时,可以选择 [2,4][2,4] 这个区间。

对于第二组数据,当 k=3k = 3 时,可以选择 [3,8][3,8] 这个区间。

对于第三组数据,没有 kk 合法。

可以证明没有更优方案。

【数据范围】

本题采用捆绑测试。

子任务编号 nn \le 特殊性质 分值
11 200200 2020
22 20002000 ^ 3030
33 10510^5 A
44 ^ 2020
  • 特殊性质 A:ai100a_i \le 100

对于所有数据,保证 1T51 \le T \le 51n1051 \le n \le 10^51ain1 \le a_i \le n