CF1304D Shortest and Longest LIS

给你一个有 $n(2 \le n \le 2\cdot 10^5)$ 个元素的排列 $A$ 中，每相邻两个元素的大小关系，要你构造出两组解，使得第一组解的 LIS 最短，第二组解的 LIS 最长。

第一行共一个整数 $t(1 \le t \le 10^4)$，表示数据组数。 每组数据包含一个整数 $n$ 以及一个长度为 $n - 1$ 的字符串 $\text{S}$。 其中 `S[i] == ''` 表示 $A_i > A_{i + 1}$。 保证所有数据中所有 $n$ 之和不超过 $2\cdot 10^5$。

输出共 $2t$ 行。 第 $2i + 1$ 行和第 $2i + 2$ 行表示第 $i$ 组数据的答案。 第 $2i + 1$ 行表示第 $i$ 组数据中 LIS 最短的解，第 $2i + 2$ 行表示第 $i$ 组数据中 LIS 最长的解。 若有多组解，可以输出其中的任意一种。 可以证明至少存在 $1$ 组解。

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.