A를 가장 최대한 큰 덩어리로 나누어 A를 정렬하는 문제입니다.

우선 k = 3인 경우는 항상 A가 정렬 가능함을 알 수 있습니다.

배열에서 최댓값을 찾아 [ … ] [ 최댓값 ] [ … ] 조각으로 나눈 뒤, 최댓값을 맨 앞으로 보내는 작업을 $N$번 반복하면 되기 때문입니다.

다음으로 k = 2인 경우가 어디에 속하는지를 확인해야 합니다.

두 조각으로 잘랐을 경우에 재배열하는 경우는 배열을 특정한 원소 기준으로 회전한 경우와 같습니다.

따라서 최솟값이 위치한 인덱스 $i$부터 인덱스 $(i + N) \bmod N$까지 순회하며 정렬이 되었는지 확인하면 됩니다.

참고

Rust의 std::iter::is_sorted는 아직 experimental입니다…

코드 
fn solve(nums: &[u32]) -> u32 {
    let mut min = std::u32::MAX;
    let mut min_pos = 0;
    for (i, &num) in nums.iter().enumerate() {
        if min > num {
            min = num;
            min_pos = i;
        }
    }
    let mut prev = 0;
    let is_sorted = nums
        .iter()
        .cycle()
        .skip(min_pos)
        .take(nums.len())
        .all(|&v| {
            let cond = prev < v;
            prev = v;
            cond
        });
    if is_sorted {
        if min_pos == 0 {
            1
        } else {
            2
        }
    } else {
        3
    }
}