输入一串数，要求你找到一个满足以下条件的 \(k\)。
- 所有小于 \(k\) 的数组成的连续子段长度要相等。
- 满足 \(1\) 的情况下段尽可能多。
- 满足前两条的情况下 \(k\) 尽可能小。
遇到这样限制很多的题目，一般考虑排个序去掉一个再考虑剩下的，所以直接排个序然后依次插入就保证满足 \(1\) 了。
那么只需要考虑怎么处理子段就行了。这题没有对一段里面数相对位置的要求，所以看成集合，用并查集即可。合并的时候顺便记录一下每个集合的大小，以及最大的，如果集合大小等于最大的的数量就是集合的数量就可以更新答案了。
代码其实很短啊，为什么其它题解看上去那么长。
// eq 是大小和最大的相等的段的数量，ml 是最大的大小，num 是集合数
void add(int x) {
flag[x] = 1;
flag[x-1] && (num --, eq -= size[find(x-1)] == ml, merge(x, x-1)),
flag[x+1] && (num --, eq -= size[find(x+1)] == ml, merge(x, x+1));
num ++;
int t = size[find(x)];
if(ml < t) eq = 1, ml = t;
else if(ml == t) eq ++;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i].v), a[i].id = i;
std::sort(a+1, a+1+n);
for(int i = 1; i <= n; i++) fa[i] = i, size[i] = 1;
for(int i = 1; i <= n; i++) {
add(a[i].id);
if(num == eq && (num > ann || (num == ann && ank > a[i].v+1)))
ank = a[i].v+1, ann = num;
}
printf("%d", ank);
}