Statement
원숭이는 수열을 비내림차순으로 정렬하는 것을 좋아한다. 하지만 원숭이는 공부를 열심히 하지 않아서, 다음과 같은 하나의 정렬 알고리즘만 사용한다.
길이가 인 수열 에 대해, 순서로 다음을 수행한다.
- 구간 에서 최솟값을 가지는 원소들 중 가장 왼쪽에 있는 원소를 라고 하자.
- 라면 아무것도 하지 않는다. 그렇지 않다면 와 를 서로 교환한다.
모두가 알다시피 개와 원숭이는 사이가 좋지 않다. 그래서 서로를 방해하거나 모함하는 데 늘 최선을 다한다. 어느 날, 원숭이는 개가 자신이 정렬해 둔 수열의 원소들을 마구 섞어 놨다며 이렇게 말했다.
"그걸 다시 정렬하는 데에 교환을 무려 번이나 해야 했다고..."
당신은 원숭이가 정렬해 둔 수열을 보고는, 원숭이가 사용하는 알고리즘의 내용을 떠올렸다. 그러자 당신은 원숭이가 거짓말로 개를 모함하고 있을 수도 있겠다는 생각이 들었다.
원숭이가 정렬해 둔 수열의 원소들을 재배열하여 만들 수 있는 수열들 중, 원숭이의 알고리즘을 적용했을 때 교환이 정확히 번 수행되는 수열이 존재하는지 알아내 보자!
Input
첫 번째 줄에 수열의 길이 과 정수 가 공백으로 구분되어 주어진다.
두 번째 줄에 비내림차순으로 정렬된 수열의 원소 이 공백으로 구분되어 주어진다.
입력으로 주어지는 모든 값은 정수이다.
Output
조건을 만족하는 수열을 한 줄에 공백으로 구분하여 출력한다. 그러한 수열이 여러 개라면 그중 아무것이나 하나 출력한다.
만약 그러한 수열이 존재하지 않는다면, 대신 The monkey lied를 출력한다.
Subtasks
Samples
Sample 1
Input
5 2
1 2 2 3 5
Output
2 1 2 5 3
Sample 2
Input
5 5
1 2 2 3 5
Output
The monkey lied