You are given a sequence of nn digits d1d2…dnd1d2…dn. You need to paint all the digits in two colors so that:
- each digit is painted either in the color 11 or in the color 22;
- if you write in a row from left to right all the digits painted in the color 11, and then after them all the digits painted in the color 22, then the resulting sequence of nn digits will be non-decreasing (that is, each next digit will be greater than or equal to the previous digit).
For example, for the sequence d=914d=914 the only valid coloring is 211211 (paint in the color 11 two last digits, paint in the color 22 the first digit). But 122122 is not a valid coloring (99 concatenated with 1414 is not a non-decreasing sequence).
It is allowed that either of the two colors is not used at all. Digits painted in the same color are not required to have consecutive positions.
Find any of the valid ways to paint the given sequence of digits or determine that it is impossible to do.Input
The first line contains a single integer tt (1≤t≤100001≤t≤10000) — the number of test cases in the input.
The first line of each test case contains an integer nn (1≤n≤2?1051≤n≤2?105) — the length of a given sequence of digits.
The next line contains a sequence of nn digits d1d2…dnd1d2…dn (0≤di≤90≤di≤9). The digits are written in a row without spaces or any other separators. The sequence can start with 0.
It is guaranteed that the sum of the values ??of nn for all test cases in the input does not exceed 2?1052?105.Output
Print tt lines — the answers to each of the test cases in the input.
If there is a solution for a test case, the corresponding output line should contain any of the valid colorings written as a string of nn digits t1t2…tnt1t2…tn (1≤ti≤21≤ti≤2), where titi is the color the ii-th digit is painted in. If there are several feasible solutions, print any of them.
If there is no solution, then the corresponding output line should contain a single character ‘-‘ (the minus sign).ExampleinputCopy
5 12 040425524644 1 0 9 123456789 2 98 3 987
outputCopy
121212211211 1 222222222 21 -
Note
In the first test case, d=040425524644d=040425524644. The output t=121212211211t=121212211211 is correct because 00224440022444 (painted in 11) concatenated with 4455644556 (painted in 22) is 002244444556002244444556 which is a sorted sequence of nn given digits.
思路：自己最开始是想从后往前找一个不递增的序列，打个标记，再从剩下的里面去找不递减的，再判断满足。然后就被hack了.hack数据：6148
错误代码：
//int main(void)
//{
// LL t;cin>>t;
// while(t--)
// {
// LL n;cin>>n;
// for(LL i=1;i<=n+100;i++) vis[i]=0;
// cin>>a+1;
// LL pos1=n;
// for(LL i=n;i>=1;i--)
// {
// if(a[pos1]>=a[i])
// {
// vis[pos1]=1;vis[i]=1;
// pos1=i;
// }
// }
// LL cnt=0;
// for(LL i=1;i<=n;i++)
// {
// if(!vis[i]) b[++cnt]=a[i];
// }
// bool flag=true;
// for(LL i=1;i<=cnt-1;i++)
// {
/// if(b[i]>b[i+1])
/// {
/// flag=false;break;
// }
// }
///
// if(!flag) cout<<"-"<<endl;
/// else
/// {
/// for(LL i=1;i<=n;i++)
/// {
/// if(vis[i]) cout<<1;
// else cout<<2;
/// }
/// cout<<endl;
/// }
// }
//return 0;
//}
正确思路：类似快排的思想，这个题字符读入，只有0-9十个可能，我们枚举x为分界点，如果a[i]<x,就放左边，a[i]>x，放右边。同时更新左边的结尾元素大小和右边的结尾元素大小。当枚举到的x==a[i]时，能放右边尽量放右边，实在不行放左边。（因为右边的比x大，能满足，而左边的比x小，比如样例的04042554644，第二个0就应该放右边，放左边就不满足了）
这题给的启示：留心题目给的数据范围小的变量，可以用来思考，作为突破口
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2e5+1000;
typedef long long LL;
char s[maxn];
LL vis[maxn];
LL n;
bool check(LL x)
{LL last1=-1;LL last2=-1;for(LL i=1;i<=n;i++){if(s[i]<x){vis[i]=1;if(s[i]<last1) return 0;last1=s[i];}else if(s[i]>x){vis[i]=2;if(last2>s[i]) return 0;last2=s[i];}else if(s[i]==x){if(s[i]>=last2) {vis[i]=2;last2=s[i];}else{vis[i]=1;last1=s[i];}}}
return 1;
}
int main(void)
{LL t;cin>>t;while(t--){cin>>n;cin>>s+1;bool flag=false;for(LL i='0';i<='9';i++){if(check(i)){flag=true;break;}}if(!flag) cout<<"-"<<endl;else{for(LL i=1;i<=n;i++) cout<<vis[i];cout<<endl;}}
return 0;
}