too hard，被吓死了，边写题解边学习。
确实是好题，没有什么完全想不到的 ad-hoc，全是完全可以发现的性质优化下来的。
学习题解：https://www.luogu.com.cn/article/25rl55k7
膜拜 Alex_Wei 大佬%%% orzorz
考虑二分答案，大于等于 \(a\) 的设为 \(1\)，否则设为 \(0\)。定义 \(0\) 的权值为 \(-1\)，\(1\) 的权值为 \(1\)，设权值前缀和 \(s_i\)，则区间 \([l,r]\) 可以通过一次操作被 \(1\) 覆盖当且仅当 \(s_r-s_{l-1}>0\)。
性质1：
设最优解方案中的一次操作 \(I_i=[l,r]\)，设 \(c(I)\) 为该区间的权值，若 \(I\neq [1,n]\)，则必然满足 \(c(I)=1\)，显然如果 \(c(I)>1\) 往外扩张一格必然合法且不劣。
性质2:
若存在合法方案，最优解必然满足 \(e\leq\lceil\log_2n\rceil\)。
感性理解即可，因为性质1，每次操作必然是 1 比 0 多一个，区间长度至少翻倍。
性质3:
设操作序列为 \(I_1,I_2,...,I_e\)，则必然满足 \(I_1\subsetneq I_2 \subsetneq...\subsetneq I_e\)。
证明不可能相交不包含：
若存在两区间 \(I_i=[a,c],I_j=[b,d],a\leq b\leq c\leq d\)，则 \(s_c-s_{a-1}+s_d-s_{b-1}=2\)，而我们替换成操作 \([a,c],[a,d]\) 则一定合法，因为填了 \([a,c]\) 后顺便把 \([b,c]\) 也填了不可能破坏合法性。
证明不可能不相交：
设 \(j\) 为最后一个满足 \(I_j\not\subsetneq I_{j+1}\) 的区间，则因为最后一次操作必然是 \([1,n]\)，一定存在 \(j+1\leq p<e\)，使得 \(I_j\cap I_p=\empty,I_j\subsetneq I_{p+1}\)。
如果 \(|I_j|\geq |I_{p}|\)，因为性质1，\(I_j\) 填的 0 比 \(I_p\) 多（或等于），则不如删掉 \(I_{j+1},I_{j+2},...,I_p\)，去扩展 \(j\)，这一定不劣。
反之同理。
按步分层处理，显然同层若两个合法区间是包含关系肯定选那个最大的，所以设 \(f_{i,l}\) 为第 \(i\) 次操作区间左端点为 \(l\) 的最大右端点。
考虑转移。
设 \(v(I)=r-l+1-(s_r-s_{l-1})\)，条件是满足 \([l,f_{i-1,l}]\subsetneq [L,R],s_R-s_{L-1}+v(I_l)\geq 1\)，移项得 \(s_R\geq s_{L-1}-v(I_l)+1\)。
这里权值大于等于 \(1\) 而不是等于 \(1\) 是因为我们目前只关注能从哪里转移是合法的，而最优性 dp 会自己调整。
从右往左扫 \(L\)，可以记录 \(g(x)\) 为满足 \(s_R\geq x\) 的最大的 \(R\)，扫一遍 \(O(n)\) 就能算。
第一次操作没有上一层，但这不重要，\(v(I_l)=0\) 自动满足选取第一次操作。
枚举 \(I_l\) 则可以获得一个 \(O(n^2\log^2n)\) 的做法，但都到这了才只有 30pts 出题人你是不是太狠了点。
观察式子发现，在 \(L\) 固定的情况下，\(v(I_l)\) 越大 \(s_R\) 下限越低，但我们要的是最大的 \(R\)，所以 \(v(I_l)\) 越大 \(R\) 越容易存在，且若已经存在了则 \(v(I_l)\) 增大不会使 \(R\) 变小（可以想象成水漫过山脉，\(v(I_l)\) 变大就是水面降低，这里的性质和后文的单调性在二维平面上分别是纵向和横向的）。
但无脑保留后缀最大是错的，因为别忘了我们还要满足 \(R\geq f_{i-1,l}\)。
猜一猜单调性？根据我们前面提到的性质（同层不包含），所以扫的过程中 \(f_{i-1,l}\) 的确是单调递减的！再看左端点 \(L\)，如果 \(L'<L,s_{L'}\leq s_{L}\)，我们肯定选 \(L'\) 转移，因为越靠前有越多区间可选，而 \(s_{L'}\leq s_L\) 保证 \(L\) 能选的 \(R\) 的集合一定包含于 \(L'\) 的。所以，向前扫的时候 \(s_L\) 单调不降。那么对于当前保留的 \(f_{i-1,l}\)，如果 \(g(s_{L-1}-v(I_l)+1)<f_{i-1,l}\) （不存在视为 \(0\)），\(g(x)\) 的限制一定会更加严苛，\(f_{i-1,l}\) 不可能再被使用，直接舍弃。
上面的逻辑，就是一个完整的单调队列过程。还是有点细节的，注释写了，看代码。
#include <bits/stdc++.h>
//#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=4e5+10;
int n,k,a[MAXN],s[MAXN],tail,head,f[MAXN],g[MAXN<<1];
bitset<MAXN> b;
pair<int,int> q[MAXN];
int c[MAXN];
inline int v(int l,int r){ return r-l+1-(s[r]-s[l-1]); }
inline bool check(int mid){int last=INT32_MAX;b.reset();for(int i=0;i<=2*n;++i){g[i]=0;}for(int i=1;i<=n;++i){s[i]=s[i-1]+(a[i]>=mid?1:-1);if(s[i-1]<last) last=s[i-1],b[i]=true;//我们要L-1断层不是L断层g[s[i]+n]=i;//防负数f[i]=i-1;//设为i-1，显然v(I_l)=0，如果设为其他值，可能会因为前缀和变成乱七八糟的值}if(s[n]==n) return true;//全是1还操作啥for(int i=2*n-1;i>=0;--i) g[i]=max(g[i+1],g[i]);for(int o=1;o<=k;++o){tail=0,head=1;for(int i=n;i>=1;--i){if(b[i]){//只在s[L-1]断层的时候更新int tmp=v(i,f[i]);while(head<=tail&&q[tail].first<=tmp) --tail;q[++tail]={tmp,f[i]};while(head<=tail&&q[head].second>g[max(0,s[i-1]-q[head].first+1+n)]) ++head;if(head<=tail) f[i]=g[max(0,s[i-1]-q[head].first+1+n)];//如果队列空了，这个点就废掉了，原封不动，以后也不会使用它}}if(f[1]==n) return true;}return false;
}
signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>k;k=min(k,__lg(n)+1);for(int i=1;i<=n;++i){cin>>a[i];c[i]=a[i];}sort(c+1,c+n+1);int N=unique(c+1,c+n+1)-c-1;int l=1,r=N,ans=1;while(l<=r){int mid=(l+r)>>1;if(check(c[mid])){ans=mid;l=mid+1;}else{r=mid-1;}}cout<<c[ans];return 0;
}
/*
好题！
好玩！
牛逼！
*/