CF1304D.Shortest and Longest LIS

Gildong recently learned how to find the longest increasing subsequence (LIS) in $O(n\log{n})$ time for a sequence of length $n$. He wants to test himself if he can implement it correctly, but he couldn't find any online judges that would do it (even though there are actually many of them). So instead he's going to make a quiz for you about making permutations of $n$ distinct integers between $1$ and $n$, inclusive, to test his code with your output.

The quiz is as follows.

Gildong provides a string of length $n-1$, consisting of characters '<' and '>' only. The $i$-th (1-indexed) character is the comparison result between the $i$-th element and the $i+1$-st element of the sequence. If the $i$-th character of the string is '<', then the $i$-th element of the sequence is less than the $i+1$-st element. If the $i$-th character of the string is '>', then the $i$-th element of the sequence is greater than the $i+1$-st element.

He wants you to find two possible sequences (not necessarily distinct) consisting of $n$ distinct integers between $1$ and $n$, inclusive, each satisfying the comparison results, where the length of the LIS of the first sequence is minimum possible, and the length of the LIS of the second sequence is maximum possible.

吉隆最近学会了如何在 $O(n\log{n})$ 时间内求出长度为 $n$ 的序列的最长递增子序列（LIS）。他想检验自己是否能正确实现该算法，但却找不到支持该功能的在线评测系统（尽管实际上这样的系统有很多）。因此，他决定为你设计一道关于排列的题目：你需要构造由 $1$ 到 $n$（含）这 $n$ 个互不相同的整数构成的排列，来测试他所写的代码。

题目如下：

吉隆给出一个长度为 $n-1$ 的字符串，该字符串仅由字符 '<' 和 '>' 组成。第 $i$ 个字符（按 1-索引）表示序列中第 $i$ 个元素与第 $i+1$ 个元素之间的大小关系。若字符串的第 $i$ 个字符为 '<'，则序列中第 $i$ 个元素小于第 $i+1$ 个元素；若为 '>'，则第 $i$ 个元素大于第 $i+1$ 个元素。

他要求你找出两个可能的序列（二者不一定不同），每个序列均由 $1$ 到 $n$（含）这 $n$ 个互不相同的整数组成，且均满足上述大小关系约束；其中第一个序列的 LIS 长度应尽可能小，第二个序列的 LIS 长度应尽可能大。

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$).

Each test case contains exactly one line, consisting of an integer and a string consisting of characters '<' and '>' only. The integer is $n$ ($2 \le n \le 2 \cdot 10^5$), the length of the permutation you need to find. The string is the comparison results explained in the description. The length of the string is $n-1$.

It is guaranteed that the sum of all $n$ in all test cases doesn't exceed $2 \cdot 10^5$.

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。

每个测试用例恰好包含一行，该行由一个整数和一个仅由字符 '<' 和 '>' 组成的字符串构成。该整数为 $n$（$2 \le n \le 2 \cdot 10^5$），表示你需要构造的排列的长度；该字符串即题目描述中所解释的比较结果，其长度为 $n-1$。

保证所有测试用例中的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print two lines with $n$ integers each. The first line is the sequence with the minimum length of the LIS, and the second line is the sequence with the maximum length of the LIS. If there are multiple answers, print any one of them. Each sequence should contain all integers between $1$ and $n$, inclusive, and should satisfy the comparison results.

It can be shown that at least one answer always exists.

对于每个测试用例，输出两行，每行包含 $n$ 个整数。第一行为最长递增子序列（LIS）长度最小的序列，第二行为最长递增子序列（LIS）长度最大的序列。若存在多个满足条件的答案，输出任意一个即可。每个序列必须恰好包含 $1$ 到 $n$（含端点）之间的所有整数，并且需满足给定的比较结果。

可以证明，至少存在一个满足条件的答案。

In the first case, $1$ $2$ $3$ is the only possible answer.

In the second case, the shortest length of the LIS is $2$, and the longest length of the LIS is $3$. In the example of the maximum LIS sequence, $4$ '$3$' $1$ $7$ '$5$' $2$ '$6$' can be one of the possible LIS.

第一种情况，唯一可能的答案是 $1$ $2$ $3$。

第二种情况，LIS 的最短长度为 $2$，最长长度为 $3$。在最长 LIS 序列的例子中，$4$ '$3$' $1$ $7$ '$5$' $2$ '$6$' 可以是其中一个可能的 LIS。