페탸와 로봇

페탸의 책장에는 $n$권의 공책이 꽂혀 있다. 공책에는 1부터 $n$까지 서로 다른 정수 번호가 붙어 있다. 페탸에게는 익숙한 배치가 있는데, 그 배치가 번호 순서와 같지 않을 수 있다. 페탸는 누군가 공책을 옮기는 것을 싫어한다. 페탸가 산 로봇은 공책의 배치를 기억하고, 그 배치의 무질서 수를 계산할 수 있다. 번호가 작은 공책이 번호가 큰 공책보다 오른쪽에 있으면 두 공책을 무질서한 쌍으로 본다. 예를 들어 배치 $(2, 1, 5, 3, 4)$에는 $(2, 1)$, $(5, 3)$, $(5, 4)$의 세 쌍이 있으므로 무질서 수는 3이다. 방을 정리한 뒤 페탸는 익숙한 배치를 잊어버렸고, 이를 복원하려고 한다. 로봇은 배치를 저장해 두었지만, 저장된 배치의 무질서 수만 알려 줄 수 있다. 페탸는 로봇에게 저장된 배치에서 두 공책의 위치를 서로 바꾸라고 요청할 수 있다. 그러면 로봇은 바뀐 배치를 저장하고, 새 배치의 무질서 수를 알려 준다. 페탸는 익숙한 배치를 복원하기에 정보가 충분하다고 판단할 때까지 요청을 반복할 수 있다. 로봇과 통신하며 익숙한 배치를 복원하는 프로그램을 작성하라.

$1 \leqslant n \leqslant 100\,000$