题目链接：戳我

一看范围1e5，往二分上想。

可是再怎么也没有想到这个神仙的二分答案qwq

我们二分一个数x，设比他大的数为1，小于等于他的数为0。那么我们就可以把原来的那个转化成一个01塔。

然后我们可以通过实验发现，如果有连续的0或者1的话，它一定会向上面推进一格qwqwq。然后谁最先占领最上面的那个格子——如果是1，就是当前枚举的答案小了，反之则大。

所以我们直接寻找哪个连续两个或以上的数离中轴线更近qwq即可。

这样子时间复杂度是木有问题，二分一个log，查询的话最劣也是O(n)。

但是有一种例外，就是01交替分布，不存在两个或以上连续的。那我们就查不到了！

不过没有关系，这种特判一下即可。第一个是0的话最终上面的就是0，第一个是1的话最终就是1。（为什么？手动绘图一下即可）

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 200010

using namespace std;

int n,l,r,mid;

int a[MAXN];

inline bool check_large(int x,int y)

{

    if(a[x]>mid&&a[y]>mid) return true;

    return false;

}

inline bool check_small(int x,int y)

{

    if(a[x]<=mid&&a[y]<=mid) return true;

    return false;

}

inline bool solve()

{

    for(int i=0;i<n-1;i++)

    {

        if(check_large(n+i,n+i+1)||check_large(n-i,n-i-1)) return true;

        if(check_small(n+i,n+i+1)||check_small(n-i,n-i-1)) return false;

    }

    if(a[1]<=mid) return false;

    else return true;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n*2-1;i++) scanf("%d",&a[i]);

    l=1,r=2*n-1;

    while(l<r)

    {

        mid=(l+r)>>1;

        if(solve()==true) l=mid+1;

        else r=mid;

    }

    printf("%d\n",l);

    return 0;

}

小蒻菜实在是没有想到这种神仙做法，表示自己还是太菜了qwqwq