B'This is the hard version of the problem. The only difference between the two versions are the allowed characters in s . You can make hacks only if both versions of the problem are solved. You are given a permutation p of length n . You are also given a string s of length n , where each character is either L, R, or ?. For each i from 1 to n : Initially, you have an undirected graph with n vertices (numbered from 1 to n ) and no edges. Then, for each i from 1 to n , add one edge to the graph: Find the maximum possible diameter over all connected ^{ text{ xe2 x88 x97}} graphs that you can form. Output -1 if it is not possible to form any connected graphs. ^{ text{ xe2 x88 x97}} Let d(s, t) denote the smallest number of edges on any path between s and t . The diameter of the graph is defined as the maximum value of d(s, t) over all pairs of vertices s and t . Each test contains multiple test cases. The first line of input contains a single integer t ( 1 <= t <= 2 cdot 10^4 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer n ( 2 <= n <= 4 cdot 10^5 ) -- the length of the permutation p . The second line of each test case contains n integers p_1,p_2, ldots, p_n ( 1 <= p_i <= n ) -- the elements of p , which are guaranteed to form a permutation. The third line of each test case contains a string s of length n . It is guaranteed that it consists only of the characters L, R, and ?. It is guaranteed that the sum of n over all test cases does not exceed 4 cdot 10^5 . For each test case, output the maximum possible diameter over all connected graphs that you form, or -1 if it is not possible to form any connected graphs. In the first test case, there are two connected graphs (the labels '...