На шахматной доске размером $$$N\times N$$$ расставлено $$$N$$$ шахматных ладей не бьющих друг друга, то есть на каждой вертикали и каждой горизонтали стоит ровно одна ладья.
Шахматную доску повернули на $$$90^\circ$$$ по часовой стрелке. Выведите получившуюся расстановку ладей.
Первая строка входных данных содержит целое число $$$N$$$, $$$1\le N\le 10^5$$$ — размер доски. Следующие $$$N$$$ строк содержат по одному числу от 1 до $$$N$$$, а именно, в $$$i$$$-й строке записано число $$$a_i$$$ — номер вертикали, в которой стоит ладья на $$$i$$$-й горизонтали. В этой задаче горизонтали нумеруются числами от 1 до $$$N$$$ сверху вниз, вертикали нумеруются числами от 1 до $$$N$$$ слева направо (см. рисунок).
Программа должна вывести $$$N$$$ чисел — расстановку ладей после поворота в таком же формате.
Решение, правильно работающее только для случаев, когда $$$N\le 5$$$, будет оцениваться в 30 баллов.
Решение, правильно работающее только для случаев, когда $$$N\le 100$$$, будет оцениваться в 60 баллов.
5 4 2 3 5 1
1 4 3 5 2
Пример в условии соответствует рисункам. Первоначально ладьи стояли в столбцах 4, 2, 3, 5, 1 при перечислении их по строкам сверху вниз. После поворота ладьи стоят в столбцах 1, 4, 3, 5, 2.
