Ночью Мирко приснилась гистограмма из
N
столбиков. Каждый из них имел ширину в 1 метр, а высоты столбиков в метрах равны
h
1
,
h
2
, ... ,
h
N
.
Вместимостью гистограммы называется максимальное количество воды (в квадратных метрах) которое она может удержать так, что конфигурация воды "стабильная", иными словами, вода в ней не перемещается под воздействием сил гравитации.
Формально, пусть количество воды над столбиками равно
v
1
,
v
2
, ... ,
v
N
соответственно. Тогда конфигурация воды стабильна, если выполняются следующие условия:
1.
h
i
+
v
i
≤
h
i
- 1
+
v
i
- 1
для каждого
i
≥ 2
, такого что
v
i
> 0
.
2.
h
i
+
v
i
≤
h
i
+ 1
+
v
i
+ 1
для каждого
i
≤
N
- 1
, такого что
v
i
> 0
.
3.
v
1
= 0
и
v
N
= 0
.
Проснувшись, Мирко захотел нарисовать такую гистограмму, чтобы высоты ее столбиков были перестановкой множества {1, 2, ... , N} и ее вместимость была в точности равна его счастливому числу
X
. Помогите Мирко и найдите такую гистограмму.
Выходные данные
Если гистограмма вместимости
X
не существует, выведите -1.
Иначе, выведите числа
h
1
,
h
2
, ... ,
h
N
(являющиеся перестановкой множества {1, 2, ... , N}), удовлетворяющие условию задачи. Если существует несколько решений, выведите любое.
Группы тестов
25 баллов —
(1 ≤
n
≤ 10)
.
25 баллов —
(0 ≤
x
≤
n - 2
)
.
50 баллов — полные ограничения.