把“移动 \(a_n\) 至数列头”称为 rotate，删除一项称为 erase。
因为要求字典序最小，所以可以逐位贪心。
考虑一个数 \(a_i\) 怎么变成第一个数：
- 使用 \(n-i\) 次
rotate/erase，再rotate一次。删除或移动原来的 \(a_{i+1}\sim a_n\)，再移动原来的 \(a_i\)（逐步移动到数列尾，再rotate一次）。 - 使用 \(i-1\) 次
erase，删除 \(a_1\sim a_{i-1}\)（逐步移动到数列头）。
设 \([a,b]_{\min}\) 表示 \(\min_{i=a}^ba_i\)，\(id(i)\) 满足 \(a_{id(i)}=i\)。
对于第一种情况：
设 \(pos=id([n-k+1,n]_{\min})\)。
则操作结束后 \(a\) 序列变为 \(a_{pos},a_{b_1},a_{b_2},\cdots,a_{b_k},a_{c_1},a_{c_2},\cdots,a_{c_m}(b_i>pos,c_i<pos,b_i<b_{i+1},c_i<c_{i+1})\)。
因为字典序最小，并且 \(a_{b_i}\) 留与不留不影响操作次数（只是用 rotate 还是 erase 的区别）
所以 \(a_{b_i}\) 要尽量小，所以可以得出 \(a_{b_i}\) 是比 \(a_{b_{i-1}}\) 更靠后而且更大的最小值。
注意到如果 \(a_{b_k}>a_{c_1}\)，那么不如对 \(a_{b_k}\) 用一次 erase 直接删掉而不是 rotate（总操作次数不变）。
所以还要满足 \(a_{b_k}<a_{c_1}\)。
所以求出 \(b_i\) 只要用单调栈，插入时 \(j\) 如果栈顶比 \(a_j\) 大就弹出栈顶。
考虑怎么求出 \(c\)：同样使用单调栈扫一遍 \([1,pos)\)，只是弹出次数限制为 \(pos-(n-k)+1\)，如果达到限制就只能插入不能弹出。可以说明这可以求出字典序最小的答案。
别忘了要保证 \(a_{b_k}<a_{c_1}\)。
对于第二种情况：
直接单调栈扫一遍 \([1,n]\)，弹出限制为 \(k\)。
输出答案时输出字典序较小的情况就可以了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int nxt[N], a[N], n, k;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i ++) cin >> a[i];
int mn = 1e9, id = n + 1;
for(int i = n - k + 1; i <= n; i ++)
if(a[i] < mn) mn = a[i], id = i;
int d = id - (n - k + 1);
int s[N] = {}, sh = 0;
// case1
int p = 1, cnt = 0;
for(p = 1, cnt = 0; p < id; p ++)
{
while(sh && cnt < d && a[s[sh]] > a[p]) sh --, cnt ++;
s[++sh] = p;
}
int ans[N] = {}, h = 0;
for(p = id; p <= n; p ++)
{
if(a[p] > a[s[1]]) continue;
while(h && a[ans[h]] > a[p]) h --;
ans[++h] = p;
}
for(int i = 1; i <= sh; i ++) ans[++h] = s[i];
// case2
sh = 0;
s[++sh] = 1;
p = 1, cnt = 0;
for(p = 2, cnt = 0; p <= n; p ++)
{
while(sh && cnt < k && a[s[sh]] > a[p]) sh --, cnt ++;
s[++sh] = p;
}
while(cnt < k) sh --, cnt ++;
bool eq = 1;
bool typ = 0;
int len = min(h, sh);
for(int i = 1; i <= len; i ++)
if(a[ans[i]] < a[s[i]]) {typ = 1; eq = 0; break;}
else if(a[ans[i]] > a[s[i]]) {eq = 0; typ = 0; break;}
if(eq && h < sh) typ = 1;
if(!typ) for(int i = 1; i <= sh; i ++) cout << a[s[i]] << " ";
else for(int i = 1; i <= h; i ++) cout << a[ans[i]] << " ";
return 0;
}