대안적 사실
시간 제한1.5초메모리 제한256 MB
배열 A를 재배열한 B를 만들어, 앞 L개 위치의 값이 원래 값과 K 이내로 차이 나도록 하면서 사전순으로 가장 큰 B를 구합니다.
문제
서기 3020년, 미국 제 237대 대통령의 취임식이 열렸다. 아니, 정확히 말하자면 대통령들의 취임식이라고 해야 할 것이다. 미국은 2884년 대선부터 N두제를 도입하여 N명의 대통령을 선출하기 때문이다.
서현이는 유명 언론사의 정치부 기자로, 모든 취임식에 참석했다. 서현이는 번째 대통령의 취임식에 참석한 사람이 명이라는 사실을 알아냈다.
이제 서현이는 이를 바탕으로 기사를 쓰려고 한다. 다만 기사의 내용이 꼭 사실일 필요는 없고, 대안적 사실이면 충분하다고 생각한다. 길이가 인 수열 가 수열 의 대안적 사실이려면 다음 두 조건을 만족해야 한다.
- 는 를 임의의 순서로 섞은 수열이다. 즉, 와 를 각각 정렬했을 때 결과가 같다.
- 모든 정수 에 대해 이다. 이때 와 은 서현이가 생각하고 있는 음이 아닌 정수이다.
서현이는 기사에 적을 대안적 사실이 가장 위대하기를 바란다. 수열 가 다른 수열 보다 위대하다는 것은 두 수열이 처음으로 달라지는 번째 항에서 임을 뜻한다. 즉, 가 보다 사전순으로 뒤에 온다는 뜻이다.
서현이를 위해 가장 위대한 대안적 사실을 찾아 주자.
입력
첫째 줄에 양의 정수 과 음이 아닌 정수 , 이 주어진다. (, , )
둘째 줄에 길이 인 수열 가 공백으로 구분되어 주어진다. ()
출력
첫째 줄에 수열 의 가장 위대한 대안적 사실을 공백으로 구분하여 출력한다.