Однажды лягушонок Вася решил отправиться в путешествие по своему родному болоту. Всего на болоте n кочек, расположенных на одной прямой. Расстояние между соседними кочками — один метр. Вася хочет за один день побывать на всех кочках, причем ровно по одному разу на каждой. Для этого он составляет маршрут — решить, в каком порядке он будет прыгать по кочкам. В качестве первой кочки Вася может выбрать любую. Он считает, что прыгать два раза на одно и то же расстояние — скучно. Поэтому он хочет, чтобы любые два прыжка по его маршруту имели разную длину. Помогите лягушонку Васе — составьте такой маршрут.
Выходные данные
Выведите n целых чисел pi (1 ≤ pi ≤ n) — маршрут лягушонка.
- Все pi должны быть попарно различны.
- Все |pi–pi + 1| должны быть попарно различны (1 ≤ i ≤ n - 1).
Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
|
1 2
|
|
2
|
3
|
1 3 2
|