Петя и Робот

У Пети на полке стоят $n$ тетрадей с полным собранием его идей. Тетради пронумерованы различными целыми числами от 1 до $n$. У Пети есть привычная расстановка тетрадей (возможно, не в порядке нумерации), и он не любит, когда кто-то их переставляет. Петя купил специального Робота, который умеет запоминать расстановку тетрадей и вычислять число беспорядков в этой расстановке.

Робот считает, что две тетради образуют беспорядок, если тетрадь с меньшим номером стоит правее тетради с бóльшим номером. Например, в расстановке $(2, 1, 5, 3, 4)$ беспорядки образуют три пары тетрадей $(2, 1)$, $(5, 3)$ и $(5, 4)$, поэтому число беспорядков в такой расстановке равно 3.

После ремонта комнаты Петя забыл привычную расстановку своих тетрадей на полке и хочет её восстановить. Робот сохранил её, но он умеет сообщать только число беспорядков в сохраненной расстановке. Петя может попросить Робота поменять местами две тетради в сохраненной расстановке. После такого запроса Робот сохранит новую расстановку и сообщит число беспорядков в ней. Петя может повторять запросы до тех пор, пока не решит, что у него достаточно информации для восстановления привычной расстановки.

Требуется составить программу, которая, общаясь с Роботом, восстанавливает привычную расстановку тетрадей.

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