Кевин — мастер задач, связанных с перестановками. Вы прогуливаетесь с Кевин в Темном лесу, и во время досуга он хочет задать вам следующий вопрос.
Даны два положительных целых числа \( n \) и \( k \), постройте перестановку\(^{\text{∗}}\) \( p \) длины \( n \), чтобы минимизировать сумму минимальных значений всех подмассивов\(^{\text{†}}\) длины \( k \). Формально, вам нужно минимизировать
\(\) \sum_{i=1}^{n-k+1}\left( \min_{j=i}^{i+k-1} p_j\right). \(\)
Выходные данные
Для каждого набора выведите \( n \) целых чисел в одной строке — перестановку \( p \), которую вы построили.
Если есть несколько ответов, вы можете вывести любой из них.
Примечание
В первом наборе, для \( k=2 \), рассмотрим все подмассивы длины \( 2 \): минимальное значение \( p_1,p_2 \) равно \( 1 \), минимальное значение \( p_2,p_3 \) равно \( 1 \), и минимальное значение \( p_3,p_4 \) равно \( 2 \). Сумма \( 1+1+2=4 \) является наименьшей среди всех возможных перестановок.
Во втором наборе все подмассивы длины \( 1 \) имеют минимальные значения \( 5, 2, 1, 6, 4, 3 \), и сумма \( 5+2+1+6+4+3=21 \) доказано является наименьшей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 2
6 1
8 3
|
3 1 2 4
5 2 1 6 4 3
4 6 2 8 3 1 5 7
|