首先考虑二分答案，把原序列变成01序列。
那么问题就相当于转换成判断能否在 \(k\) 次操作内，将序列变成全 \(1\)。
由于每次操作一定可以做到把 \(1\) 的个数\(n\)变成 \(n'=2n-1\)。因此可以得知操作一定是 \(\log n\) 级别的。
但是这个问题仍然不太好做，很多贪心都是假的。考虑最暴力的区间DP。
由于多选 \(1\) 一定不劣，所以操作区间一定互相不交。
因为如果要相交，一定比包含关系劣。
设 \(f[i][l][r]\) 表示使用 \(i\) 步能否将 \([l,r]\) 变成全 \(1\)。
考虑转移，最简单的思路就是枚举最右的区间：\(f[i][l][r]|=f[x][l][k]\&f[y][k+1][r],x+y=i\)。
特殊做一下 \(f[i][l'][r']|=f[i-1][l][r]\)。
但是分析 \(f[x][l][k]\) 和 \(f[y][k+1][r]\) 这两个状态，假设 \(k-l+1<=r-k\)。
那么显然 \(f[y][k+1][r]\) 是可以转移到 \(f[y+1][l'][r],(l'\le l)\)，这样操作更优秀。
所以以此类推，不如将 \(x\) 次操作全部给 \(f[y][k+1][r]\)。
那么如此，就可以贪心地分析得到每次转移只会从一个区间转移而来。
转移式就直接变成了 \(f[i][l'][r']|=f[i-1][l][r]\)。
也就是说，如果将操作区间建树，那么就是一条链。形成包含关系。
这样就可以改进状态为，设 \(f[i][r]\) 表示用 \(i\) 次操作，只考虑 \([1,r]\)，最小的 \(l\)，使得 \([l,r]\) 可以全变为 \(1\)。
这个就属于线性DP 了。
转移式：\(f[i][r]=\min(P[r][u][f[i-1][u]]),lim[r]\le u\le i\)。
这里转移式的思路是找到上一层操作区间的右端点，左端点。
可以计算出以\(r\)为操作区间右端点最远的左端点 \(l=P[r][u][f[i-1][u]]\)。
具体可以自行推得，并不困难。
这里 \(P[r][u][f[i-1][u]]\) 的用意就是表示这个 \(l\) 与 \(r\)，\(u\)，\(f[i-1][u]\) 相关。同理 \(lim[r]\) 表示仅与 \(r\) 相关。（这里都忽视了 \(i\) 这个状态）
考虑使用单调队列优化转移，因为发现将越多的 \(0\) 变成 \(1\) 的决策点越优。这个可以由 \(l\) 的表达式看出。
而 \(u\) 是否合法则与 \(f[i-1][u]\) 相关，并非随 \(u\) 递增。
因此在入队时需要注意判断。
至于 \(lim[r]\)，是与前缀 \(1\) 的个数和 \(0\) 的个数差相关。
因为这个差的变化为 \(1\) 或 \(-1\)，\(lim[r]\) 的变化量最多为 \(1\)。所以可以暴力扫单调队列的队头。
具体这部分的详细细节可以看代码或看出题人题解。
那么这题就做完了，时间复杂度为 \(O(n\log^2 n)\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<stack>
#include<bitset>
#include<random>
#include<unordered_map>
#include<deque>
#include<cassert>
#include<chrono>
using namespace std;
#define re int
inline int read(){
int x=0,ff=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')ff=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}
return x*ff;
}
int n,k,a[400005],c[400005],s[400005],ss[400005],f[400005],g[400005],p[400005];
int dl[400005],tot,cnt,b[800005];
bool ok(int xx){
for(re i=1;i<=n;i++){
if(a[i]>=xx)c[i]=1;
else c[i]=0;
s[i]=s[i-1]+c[i];
ss[i]=ss[i-1]+(c[i]?1:-1);
//cout<<c[i]<<" ";
}//puts("");
if(s[n]<2)return 0;
memset(b,0x3f,sizeof(b));
for(re i=n;i;i--)b[ss[i]+n]=i;
b[n]=0;
for(re i=1-n;i<=n;i++)b[i+n]=min(b[i+n],b[i+n-1]);
f[0]=1;
for(re i=1;i<=n;i++){
if(c[i])f[i]=f[i-1];
else f[i]=i+1;
}
if(f[n]==1)return 1;
for(re i=1;i<=21&&i<=k;i++){
for(re j=1;j<=n;j++)g[j]=f[j],p[j]=j-g[j]+1-(s[j]-s[g[j]-1]);
tot=1;cnt=0;
for(re j=1;j<=n;j++){
if(f[j]<=j){
while(cnt&&p[j]>=p[dl[cnt]])cnt--;
if(!cnt||(-s[g[j]-1]+p[j])*2+g[j]>=(-s[g[dl[cnt]]-1]+p[dl[cnt]])*2+g[dl[cnt]])dl[++cnt]=j;
tot=min(tot,cnt);
}
while(tot<=cnt&&(s[j]-s[g[dl[tot]]-1]+p[dl[tot]])*2<=(j-g[dl[tot]]+1))tot++;
if(tot<=cnt){
while(tot&&(s[j]-s[g[dl[tot]]-1]+p[dl[tot]])*2>(j-g[dl[tot]]+1))tot--;
tot++;
}
if(f[j]>j)f[j]=b[ss[j]-1+n]+1;
if(tot<=cnt){
f[j]=min(b[ss[j]+p[dl[tot]]*2-1+n]+1,f[j]);
//if(f[j]>g[dl[tot]])f[j]=1;
}
f[j]=min(f[j],g[j]);
}
if(f[n]==1)return 1;
}
return 0;
}
signed main(){
n=read();k=read();
for(re i=1;i<=n;i++)a[i]=read();
if(n==1){cout<<a[1]<<endl;return 0;}
int l=0,r=1e9,mid;//cout<<ok(939);return 0;
while(l<=r){
mid=(l+r)>>1;
if(ok(mid))l=mid+1;
else r=mid-1;
}
cout<<l-1<<endl;
return 0;
}