Фермер Джон пытается отсортировать свои \(N\) коров (\(1 \leq N \leq 100\)),
последовательно пронумерованных \(1 \dots N\).
В настоящий момент коровы выстроились в линию в порядке
\(p_1, p_2, p_3, \dots, p_N\), и ФД стоит перед коровой \(p_1\).
Он хочет переупорядочить коров так, чтобы они стали в порядке
\(1, 2, 3, \dots, N\), с коровой \(1\) перед ФД.
Фермера Джона слышит только корова, которая стоит перед ним.
В этот момент ФД может сказать ей перейти на \(k\) позиций назад
(\(k\) в интервале \(1 \ldots N-1\).). \(k\) коров, которых она проходит,
двигаются вперёд, освобождая место для неё, в которое она и
становится.
Например, пусть \(N=4\) и коровы стоят в таком порядке
ФД: 4, 3, 2, 1
Единственная корова, которая слышит ФД, это корова \(4\).
Если он скажет ей сдвинуться на 2 позиции, порядок станет таким:
ФД: 3, 2, 4, 1
Теперь ФД слышит только корова \(3\). Теперь ей можно давать инструкцию и т.д.
Определите последовательность инструкций (с минимальным их количеством),
которые должен дать ФД, чтобы отсортировать всех коров.
ФОРМАТ ВВОДА (файл sleepy.in):
Первая строка содержит \(N\). Вторая строка содержит \(N\) целых чисел,
разделённых одиночными пробелами : \(p_1, p_2, p_3, \dots, p_N\),
указывающих стартовый порядок коров.
ФОРМАТ ВЫВОДА (файл sleepy.out):
Первая строка должна содержать одно целое число
\(K\), задающее минимальное
количество инструкций, которое требуется, чтобы отсортировать всех коров.
Вторая строка должна содержать \(K\) разделённых одиночными пробелами
целых чисел \(c_1, c_2, \dots, c_K\), каждое в интервале \(1 \ldots N-1\),
задающих последовательность инструкций, которая отсортирует исходную
последовательность коров.
Если имеется несколько оптимальных последовательностей инструкций,
выведите любую.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 4 3
|
3
2 2 3
|