The proof of why we only need to consider two cases can be seen in the official editorial and I will not repeat it here.

Here I want to discuss how to achieve \(\mathcal{O}(N)\) time complexity. Actually, it is very easy.

Suppose that we have determined the leading term will be lead and its original position is pos[lead] (0-indexed).

For the case where no rotation is done, we need to erase pos[lead] times to make it the leading term. Then we have k-pos[lead] operations left. We can mimic a monotonic stack here: if we have operations remaining, and the current tail is larger than the next number to be added, we just erase the current tail. We repeat this until we have no operations left or the current tail is smaller than the next number. Then we push the next number.

For the case where there are rotations, we need to first rotate n-pos[lead] times to make lead the leading term. The following part becomes a bit trickier because, for the numbers that originally follow lead, we do not need extra operations to erase them (since they have already been counted in the rotation). So when we maintain the “monotonic stack”, we first check whether the number to be erased originally follows lead, and do not use operations in that case.

Sample code (Rust)

use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n: usize,
        k: usize,
        p: [Usize1; n],
    }

    let mut pos = vec![0usize; n];
    for i in 0..n {
        pos[p[i]] = i;
    }

    let mut leading = n;
    for i in 0..=k {
        leading = leading.min(p[i]);
    }
    for i in n - k..n {
        leading = leading.min(p[i]);
    }

    let mut ans = vec![n];
    
    // no rotations
    if pos[leading] <= k {
        let p1: Vec<usize> = p[pos[leading]..].to_vec();
        let mut k1 = k - pos[leading];
        let mut v1 = vec![leading];
        for i in 1..p1.len() {
            while v1[v1.len() - 1] > p1[i] && k1 > 0 {
                k1 -= 1;
                v1.pop();
            }
            v1.push(p1[i]);
        }

        while k1 > 0 {
            v1.pop();
            k1 -= 1;
        }
        ans = ans.min(v1);
    }

    // rotate first
    if n - pos[leading] <= k {
        let p2 = [p[pos[leading]..].to_vec(), p[..pos[leading]].to_vec()].concat();
        let mut k2 = k - (n - pos[leading]);
        let mut v2 = vec![leading];
        for i in 1..p2.len() {
            while v2[v2.len() - 1] > p2[i] {
                if pos[v2[v2.len() - 1]] > pos[leading] {
                    v2.pop();
                } else if k2 > 0 {
                    k2 -= 1;
                    v2.pop();
                } else {
                    break;
                }
            }
            v2.push(p2[i]);
        }
        while k2 > 0 {
            v2.pop();
            k2 -= 1;
        }
        ans = ans.min(v2);
    }

    println!(
        "{}",
        ans.into_iter()
            .map(|x| (x + 1).to_string())
            .collect::<Vec<String>>()
            .join(" ")
    );
}