TESSER  Finding the Tesserect
Dr. Bruce Banner had estimated a coarse location of Tesseract through gamma radiation emission tracing experiment. It was estimated that Tesseract was hidden somewhere within the Alps mountains. Captain America was given the assignment to look for the Tesseract and bring it back to S.H.I.E.L.D. While roaming through the mountains of Alps, Captain America looked at the height of hills and clicked a panoramic photograph of mountains. This gives an idea of the heights of mountains. Meanwhile Banner was able to determine a continuous pattern of mountains behind which the Tesseract lies and transmitted a message containing the pattern.
The message is a string consisting of characters 'G' , 'L' and 'E' where G means greater, L means less and E means equal. But this estimation is likely to go wrong due to not considering environmental disturbances that may have arisen in the medium during the experiment.
Pattern estimate is correct only if one can find a set of consecutive heights out of the given N heights satisfying the message pattern (if G is first character of the message string then second height should be greater than the first height of the selected set and so on) Captain America seeks your help to find out whether the estimation is correct or wrong so that Captain America could proceed his tasks.
Input
The first line of the input contains an integer T denoting the number of test cases. Each test case consists of 3 lines. The first line of each test case contains a single integer N denoting the number of hills. Second line of each test case consists of N integers (a_1,a_2....a_n), the heights of hills. Third line contains the message pattern.
 1 ≤ T ≤ 10^{5}
 2 ≤ N ≤ 10^{5}
 1 ≤ a_i ≤ 10^{9}
 1 ≤ Length of Message Pattern ≤ N1
Output
For each test case print 'YES' if the pattern estimation is correct. Else print 'NO'.
Example
Input: 1 5 1 2 3 4 1 GGL Output: YES
Explanation
Answer is "YES", because 2 3 4 1 satisfies GGL pattern, i.e. 3 is greater than 2, 4 is greater than 3, 1 is less than 4.
hide comments
sleepy_coder:
20200619 01:43:54
KMP really rocks...!!! 

amansahu112:
20200419 20:15:52
AC IN 1 GO.


mohityadav7:
20180313 15:22:09
Last edit: 20180313 15:22:27 

rohit9934:
20180117 10:21:12
if you are getting TLE with strings in c++, pick c++ 14 (6.3) as your language. 

sagar_zhcet:
20170628 11:37:44
KMP rocks ;) 

steady_bunny:
20170616 19:16:01
working with string causes TLE whereas array of char works perfectly 

vengatesh15:
20170210 09:28:23
Easy one AC in 1 go ☺️☺️ 

Deepak :
20160519 21:45:22
AC in one go .. ;) 

Dushyant Singh:
20150529 11:12:58
TLE 

Abhilash:
20150402 20:23:55
one go AC :) Last edit: 20150402 20:26:46 
Added by:  BLANKRK 
Date:  20131114 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Code Weavers 2013 