Гильдон недавно научился искать Наибольшую Возрастающую Подпоследовательность (НВП) за \(O(n\log{n})\) для последовательности длины \(n\). Он решил проверить себя, может ли он реализовать этот алгоритм корректно, но он не смог найти эту задачу ни в одном архиве (ни смотря на то, что на самом деле, она есть во многих). Так что вместо этого он решил загадать вам загадку на построение последовательности из \(n\) различных целых чисел от \(1\) до \(n\), включительно, чтобы протестировать своим кодом ваш ответ.
Опишем загадку.
Гильдонг дает вам строку длины \(n-1\), состоящую только из символов '<' и '>'. \(i\)-й (в 1-индексации) символ это результат сравнения \(i\)-го и \(i+1\)-го элемента последовательности. Если \(i\)-й символ строки это '<', тогда \(i\)-й элемент последовательности меньше чем \(i+1\)-й. Иначе, \(i\)-й символ строки '>', и \(i\)-й элемент последовательности больше чем \(i+1\)-й элемент.
Он просит вас найти два возможные последовательности (не обязательно различных) состоящих из \(n\) различных целых чисел от \(1\) до \(n\), включительно, что обе последовательности удовлетворяют всем результатам сравнения, и длина НВП первой последовательности минимально возможная, а длина НВП второй последовательности максимально возможная.
Выходные данные
Для каждого тестового случая, выведите две строки, по \(n\) целых чисел в каждой. Первая строка должна содержать последовательность с минимальной НВП, а вторая строка последовательность с максимальным НВП. Если есть несколько возможных ответов, вы можете вывести любой. Каждая последовательность должна содержать все целые числа от \(1\) до \(n\), включительно, и должна удовлетворять всем результатам сравнения.
Можно показать, что всегда найдется хотя бы один ответ.
Примечание
В первом тестовом случае, \(1\) \(2\) \(3\) это единственный возможный ответ.
Во втором тестовом случае, наименьшая длина НВП это \(2\), а наибольшая это \(3\). Для примера с наибольшей НВП, \(4\) '\(3\)' \(1\) \(7\) '\(5\)' \(2\) '\(6\)'может быть одной из возможных НВП.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 <<
7 >><>><
5 >>><
|
1 2 3
1 2 3
5 4 3 7 2 1 6
4 3 1 7 5 2 6
4 3 2 1 5
5 4 2 1 3
|