Сортировка очередями
Очередь - структура данных, основанная на принципе «первый пришел - первый вышел» (FIFO, First In - First Out). Добавление элемента возможно только в конец очереди, извлечение - только из начала очереди. Таким образом, элементы извлекаются из очереди в том же порядке, в котором они были в нее добавлены.
Задача сортировки состоит в упорядочивании заданного массива чисел (или других объектов) по возрастанию или убыванию. У этой задачи существует достаточно многих вариантов, для многих из которых существуют весьма эффективные алгоритмы.
Далее в задаче рассматривается специальное устройство, содержащее входной поток, выходной поток и k очередей, пронумерованных числами от 1 до k.
Ваша задача состоит в том, чтобы по заданной последовательности различных чисел, которую требуется отсортировать, составить программу для этого устройства, которая будет выводить в выходной поток те же числа, что поступили во входной поток, но упорядоченные по возрастанию.
Программа должна содержать ровно 2n операций, каждая из которых либо читает число из входного потока и добавляет его в одну из очередей, либо извлекает число из одной из очередей и выводит его в выходной поток.
Обратите внимание, что нельзя выполнять операции извлечения из очередей, пока не будут закончены все операции добавления.
Входные данные
Первая строка содержит целое число n (1 ≤ n ≤ 300). Вторая строка содержит n различных целых чисел a[1], ..., a[n] в том порядке, в котором они поступают из входного потока (1 ≤ a[i] ≤ 10^9 для всех i от 1 до n). Третья строка содержит целое число k (1 ≤ k ≤ n).
Выходные данные
Если сортировку выполнить невозможно, выведите слово NO.
Иначе выведите слово YES и 2n строк, задающих программу сортировки. Каждая из этих строк должна описывать одну операцию и иметь следующий формат:
I(j) - считать элемент из входного потока и добавить его в очередь номер j (1 ≤ j ≤ k);
R(j) - извлечь элемент из очереди номер j (1 ≤ j ≤ k) и вывести его в выходной поток.