# D. Shortest and Longest LIS

Codeforces Round 620 (Div. 2) D. Shortest and Longest LIS

## Description

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.

Input
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$.

Output
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.

Example

input
3
3 <<
7 >><>><
5 >>><
output
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
Note
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.

## Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], b[maxn];//用a记录最短,b记录最长
int main()
{
ios::sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n; string s;
cin >> n >> s;
int num, last;
/*我们首先处理最短的，把num的初始值赋为n（即当前能达到的最大值），last记录的是新的划分开始的位置，用当前位置i减去last即为这一个划分的元素个数*/
num = n, last = 0;
for (int i = 0; i < n; i++) {
if (i == n - 1 || s[i] == '>') {//根据s[i]='>'进行划分，同时因为可能出现最后一位是<的情况，我们也需要考虑遍历到最后一位时直接进行赋值
for (int j = i; j >= last; j--)//从当前能达到的最大值进行赋值，i到last（即当前的一个划分）
a[j] = num--;//因为根据">"划分，所以每一个划分里面的元素都是递增的，所以我们需要倒着赋值，每次取当前能取到的最大值(即num--)
last = i + 1;//每次last更新新划分的开始
}
}
/*然后我们处理最长的，代码，变量含义作用跟上面基本一样，不同的是，num我们要从当前能达到的最小的开始赋值*/
num = 1, last = 0;
for (int i = 0; i < n; i++) {
if (i == n - 1 || s[i] == '<') {
for (int j = i; j >= last; j--)
b[j] = num++;//因为根据"<"划分，所以每一个划分里面的元素都是递减的，所以我们需要倒着赋值，每次取当前能取到的最小值(即num++)
last = i + 1;
}
}
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
for (int i = 0; i < n; i++)
cout << b[i] << " ";
cout << endl;
}
}