요소바꾸기

n 개의 정수 arr의 배열이 ​​주어지면, 최대 k개의 요소바꾸기를 수행한 후 얻을 수 있는 lexicographically smallest sequence(사전적으로 가장 작은 시퀀스)를 찾아야 합니다. 요소바꾸기는 배열에서 한 쌍의 연속 배열요소를 서로 바꾸는 작업입니다.

참고 : Lexicographically smallest sequence는 다음과 같이 정의됩니다. 배열의 가장 작은 요소가 배열의 시작점 arr[0]에 있고 다음으로 작은 요소가 arr[1]에 있는 배열입니다. Lexicographically smallest sequence는 바로 옆의 요소들을 서로 교환하여 얻을 수 있습니다. 인덱스 i와 j인 요소에서 (i > j일 경우) 교환해야 하는 갯수는 i - j입니다.

두개의 동일한 길이의 배열 x, y에서 배열 x는 다음과 같은 경우 다른 배열 y보다 lexicographically smaller라고 할 수 있습니다. 두 배열의 각 해당 인덱스의 x 배열요소가 y 배열의 요소보다 작습니다.

최대 k개의 교환 후, 최대한 lexicographically smallest 시퀀스를 달성할 수 있는 배열을 반환합니다.

예제 1

입력

k = 3  
arr = [8, 9, 11, 2, 1]  

출력

[2, 8, 9, 11, 1]

// [11, 2], [9, 2], [8, 2] 순으로 바꿀 수 있습니다.

예제 2

입력

k = 2  
arr = [5, 3, 1]  

출력

[1, 5, 3]

// 3 <--> 1 교환 후 5 <--> 1 교환
// [1, 5, 3]은 최대 2 번의 스왑후 만들 수 있는
// lexicographically 가장 작은 시퀀스입니다.