В вагон метро, представляющий из себя единственный ряд из $$$n$$$ сидений, заходят по очереди $$$n$$$ человек. Так как каждый из пассажиров не любит сидеть рядом с другими людьми, заходящие пассажиры выбирают себе пустое место, расстояние от которого до ближайшего занятого места минимально. В случае, если таких мест несколько, пассажир сядет на ближайшее к входу в вагон место.
Пронумеруем заходящих в вагон людей от $$$1$$$ до $$$n$$$ в порядке их входа, а итоговую рассадку в вагоне представим массивом чисел, где вход в вагон будет перед первым элементом массива, а на $$$i$$$-й позиции будет номер человека, который сел на $$$i$$$-е место.
Определите, как в итоге рассядутся люди, заходящие в вагон с $$$n$$$ пустыми местами.
В единственной строке входных данных содержится одно целое число $$$n$$$ ($$$1 \leq n \leq 100$$$) — количество сидений в вагоне и человек, которые зайдут в него по очереди.
В единственной строке выходных данных выведите $$$n$$$ чисел через пробел: $$$i$$$-е число должно быть равно номеру человека, выбравшего $$$i$$$-е место.
5
1 4 3 5 2
6
1 4 3 5 6 2
11
1 6 4 7 8 3 9 5 10 11 2
12
1 6 5 7 8 3 9 10 4 11 12 2
В первом примере из условия пассажиры выбирают места следующим образом: