There is an array
with elements. Each element of has a fixed polarity: either north or south.
Chef is allowed to perform some (possibly zero) operations on the array . In one operation, Chef can:
- Pick some subarray of array , such that, the first and last elements of the subarray have different polarities, and, rearrange the elements in this subarray any way he wants.
Note that the polarity of each element remains unchanged after an operation.
Find the minimum number of operations required to sort the array in non-decreasing order, or state that it is impossible.
A subarray of is obtained by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
Input Format
- The first line contains an integer , denoting the number of test cases. The test cases then follow.
- The first line of each test case contains a single integer .
- The second line of each test case contains space-separated integers .
- The third line of each test case contains a string of length , the th character of which is either or , representing that the th element of has north or south polarity, respectively.
Output Format
For each test case, if it impossible to sort the array, output . Otherwise, output a single integer: the minimum number of operations required to sort the array.
Constraints
- The sum of across all test cases doesn't exceed .
Subtasks
Subtask #1 (100 points): original constraints
Sample Input 1
6
5
1 3 2 3 7
NNSNS
2
2 1
SS
3
1 8 12
SNS
3
3 2 1
NSN
5
1 2 3 5 4
NSNSN
5
1 1 2 2 1
SNSNN
Sample Output 1
1
-1
0
2
1
1
Explanation
Let's represent elements with a polarity of north in , and elements with a polarity of south in . The polarity of each element is also labelled above it.
In the first test case, we can sort the array in a single operation as follows.
- Rearrange the subarray : .
In the second test case, the array cannot be sorted, since no operations can be performed.
In the third test case, the array is already sorted, so the answer is .
In the fourth test case, we can sort the array in two operations as follows.
- Rearrange the subarray : .
- Rearrange the subarray : .
No comments:
Post a Comment