Рассмотрим перестановку\(^{\text{∗}}\) \(p_1, p_2, \ldots, p_n\) чисел от \(1\) до \(n\). Введём следующую сумму\(^{\text{†}}\):
\(\)S(p) = \sum_{1 \le l \le r \le n} \min(p_l, p_{l + 1}, \ldots, p_r)\(\)
Рассмотрим все перестановки длины \(n\) с максимальным значением \(S(p)\). Необходимо вывести \(k\)-ю из них в лексикографическом\(^{\text{‡}}\) порядке, или сообщить, что их меньше \(k\).
Выходные данные
Для каждого набора входных данных, если подходящих перестановок меньше \(k\), выведите \(-1\).
Иначе выведите \(k\)-ю подходящую перестановку.
Примечание
Посчитаем искомую сумму для всех перестановок длины \(3\) в лексикографическом порядке:
| Перестановка | Значение \(S(p)\) |
| \([1, 2, 3]\) | \(10\) |
| \([1, 3, 2]\) | \(10\) |
| \([2, 1, 3]\) | \(9\) |
| \([2, 3, 1]\) | \(10\) |
| \([3, 1, 2]\) | \(9\) |
| \([3, 2, 1]\) | \(10\) |
В первом наборе необходимо вывести вторую подходящую перестановку длины \(3\). Посмотрев на таблицу, мы видим, что это перестановка \([1, 3, 2]\).
Во втором наборе необходимо вывести третью подходящую перестановку длины \(3\). Посмотрев на таблицу, мы видим, что это перестановка \([2, 3, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 2
3 3
4 11
4 6
6 39
7 34
|
1 3 2
2 3 1
-1
2 4 3 1
-1
2 3 4 5 7 6 1
|