CF1304D Shortest and Longest LIS

Gildong 最近学会了如何用 $O(n\log n)$ 的时间求出长度为 $n$ 的序列的 [最长上升子序列](https://en.wikipedia.org/wiki/Longest_increasing_subsequence)（LIS）。他想测试自己是否能正确实现该算法，但找不到任何在线评测平台来测试（尽管实际上有很多）。于是他转而为你准备了一个小测验：你需要构造由 $1$ 到 $n$ 之间 $n$ 个互不相同的整数组成的排列，以帮助他检验代码的正确性。 测验内容如下： Gildong 会给出一个长度为 $n-1$ 的字符串，仅由字符 `` 组成。字符串的第 $i$ 个字符（从 1 开始编号）表示序列中第 $i$ 个元素与第 $i+1$ 个元素之间的大小关系。如果该字符是 ``，则第 $i$ 个元素大于第 $i+1$ 个元素。 他要求你找出两个可能的序列（不一定不同），每个序列都由 $1$ 到 $n$ 之间的 $n$ 个互不相同的整数组成，并且都满足上述大小关系；其中第一个序列的 LIS 长度要尽可能短，第二个序列的 LIS 长度要尽可能长。

每个测试点包含一个或多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例单独占一行，包含一个整数 $n$ 和一个仅由 `` 组成的字符串。整数 $n$（$2 \le n \le 2 \cdot 10^5$）表示需要构造的排列的长度。字符串即为题目描述中说明的大小关系，其长度为 $n-1$。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出两行，每行包含 $n$ 个整数。第一行是 LIS 长度最小的序列，第二行是 LIS 长度最大的序列。如果存在多组解，输出任意一组即可。每个序列必须包含 $1$ 到 $n$ 之间的所有整数，并且满足所给的大小关系。 可以证明至少有一组解总是存在。

在第一个样例中，$1\ 2\ 3$ 是唯一可能的答案。 在第二个样例中，最短的 LIS 长度为 $2$，最长的 LIS 长度为 $3$。在最长 LIS 序列的样例中，`4 '3' 1 7 '5' 2 '6'` 是可能的 LIS 之一（原文中的单引号仅为分隔，实际输出无引号）。 由 deepseek 翻译