안무

주라: 트브르트코, 어제 공연은 어땠어?

트브르트코: 아주 좋았어. 가장 좋았던 건 1000명의 무용수가 왼쪽에서 오른쪽으로 한 줄로 서서 안무를 시작했을 때였어. 각자 의상에 $1$부터 $1000$ 사이의 번호가 적혀 있었고, 번호는 모두 달랐어. 그런데 솔직히 말하면, 줄을 서 있는 그들을 보니 순서가 마음에 들지 않았어.

주라: 무슨 말이야?

트브르트코: 줄에서 연속된 무용수 구간을 하나 골라서, 앞 위치에 있는 무용수의 번호가 뒤 위치의 무용수 번호보다 큰 쌍이 몇 개인지 세어 봤어. 그 쌍의 개수가 홀수면 마음에 들어.

주라: 아이고, 트브르트코, 전체를 봐야지. 판단은 내가 할게. 그래서 번호들이 차례로 어떻게 놓여 있었는데?

트브르트코: 음... 그건 잊어버렸어. 그래도 연속된 무용수 구간마다 마음에 들었는지 아닌지는 말해 줄 수 있어.

주라: 그렇군. 그럼 그 정보를 바탕으로 번호를 알아내 보는 수밖에 없겠네.