As you know, war is going on between Russia and Ukraine. There are a total of n cities in Russia.
Vladimir Putin (President of Russia) wanted exact data of number of troops in each city, but he only got data for some of the cities, which is given to you as an array.
You are given an array where the ith element of array denote the number of troops in the ith city, If some value is -1, it signifies we don’t have data for that city.
A wellwisher of Vladimir Putin told him that he can win the war, if troops of the n cities follow the pattern specified by a string he will give.
The string has n-1 characters, with each character representing the relation between number of troops for every 2 adjacent cities in the array.
The string will contain only 3 characters - ‘G’ , ‘E’ , ‘L’, which indicates the following:
- ‘G’ if (i)th city should have strictly more number of troops than (i+1)th city.
- ‘E’ if (i)th city should have equal number of troops as (i+1)th city.
- ‘L’ if (i+1)th city should have more number of troops than (i)th city.
In order to satisfy the pattern in the string, you can put any number of troops in the cities where you don’t have data (i.e where a[i] = -1)
Confirm if there is at least one way to change the array, such that the pattern indicated by the String can be satisfied and Putin can win the war. Else, say that it cannot be done and Putin cannot win the war.
For example, let’s say string s = “GGELG”
If we have the initial troops array as this: 8 6 -1 -1 -1 11
One possible way to change the -1s is this: 8 6 5 5 12 11, such that the pattern is satisfied
With the modified array, 8 is greater(G) than 6, 6 is Greater(G) than 5, 5 is equal(E) to 5, 5 is Less(L) than 12, 12 is Greater(G) than 11.
So, the answer will be YES for it.
Input Format
First line contain T - number of test cases.
Every test contain N - number of cities
then N line contains number of troops in every city,
and last line contain string given by well wisher
Constraints
1 ≤ T≤ 1,000
2 ≤N ≤10^5
−1≤Ai≤106 for each valid i
|S|=N−1
S contains only characters ‘G’, ‘E’ and ‘L’
the sum of N over all test cases does not exceed 10^6
Output Format
For every test, print YES if some values exist which satisfy the pattern in string, else print NO
Sample Input 0
2 6 8 6 -1 -1 -1 11 GGELG 5 4 -1 -1 -1 7 LLLL
Sample Output 0
YES NO
Can Anyone tell me how to approach this question