도서관
시간 제한2초메모리 제한512 MB
숨겨진 N권의 책 순열이 있고, 책 번호 집합을 질의하면 그 책들만 꺼내는 데 필요한 최소 연속 구간 제거 횟수를 돌려주는 오라클이 있다. 최대 20000번의 질의로 순서를 알아낸다. (좌우 반전은 구분하지 않는다.)
문제
수백 년이 지난 뒤, JOI 도시는 폐허가 되었다. 탐험가 IOI찬은 도서관이 세워졌던 지역을 탐험하고 있다. 탐험 결과로 다음과 같은 사실이 밝혀졌다.
- JOI 도시 도서관의 책장에는 N권의 책이 있었다. N권의 책은 책장에 왼쪽에서 오른쪽으로 일렬로 꽂혀 있었다.
- N권의 책에는 1번부터 N번까지 번호가 매겨져 있었다. 하지만 책장에서 책이 놓인 순서는 책 번호의 순서와 다를 수 있다.
- 한 번의 조작으로 책장에서 연속해 놓인 책들을 한꺼번에 꺼낼 수 있었다.
안타깝게도 IOI찬은 도서관에서 옛날 책을 찾지 못했다. 대신 그녀는 도서관 책장의 조작을 관리하던 기계를 발견했다. 책의 번호로 하나 이상의 책을 지정해 기계에 질의를 보내면, 기계는 책장에서 그 책들만 꺼내는 데 필요한 최소 조작 횟수를 답한다.
IOI찬은 기계에 질의를 보내 책장에서 책이 놓인 순서를 알아내려고 한다. 하지만 N권의 책 순서를 뒤집어도 기계의 답은 같으므로, 책이 왼쪽에서 오른쪽으로 놓였는지 오른쪽에서 왼쪽으로 놓였는지는 알아낼 필요가 없다.
기계가 낡았기 때문에 질의는 최대 20 000번까지 보낼 수 있다.
기계에 최대 20 000번의 질의를 보내 책장에서 책이 놓인 순서를 알아내는 프로그램을 작성하라. 책이 왼쪽에서 오른쪽으로 놓였는지 오른쪽에서 왼쪽으로 놓였는지는 알아내지 않아도 된다.
제한
- 1 ≤ N ≤ 1 000.
- 1 ≤ Ai ≤ N (1 ≤ i ≤ N).
- Ai ≠ Aj (1 ≤ i < j ≤ N).