#P1987G2. Spinning Round (Hard Version)
Spinning Round (Hard Version)
Description
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$:
- Define $l_i$ as the largest index $j < i$ such that $p_j > p_i$. If there is no such index, $l_i := i$.
- Define $r_i$ as the smallest index $j > i$ such that $p_j > p_i$. If there is no such index, $r_i := i$.
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:
- If $s_i =$ L, add the edge $(i, l_i)$ to the graph.
- If $s_i =$ R, add the edge $(i, r_i)$ to the graph.
- If $s_i =$ ?, either add the edge $(i, l_i)$ or the edge $(i, r_i)$ to the graph at your choice.
Find the maximum possible diameter over all connected$^{\text{∗}}$ graphs that you can form. Output $-1$ if it is not possible to form any connected graphs.
$^{\text{∗}}$ 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 \le t \le 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 \le n \le 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 \le p_i \le 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.
Input
Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 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 \le n \le 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 \le p_i \le 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$.
Output
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.
8
5
2 1 4 3 5
R?RL?
2
1 2
LR
3
3 1 2
L?R
7
5 3 1 6 4 2 7
?R?R?R?
5
5 2 1 3 4
?????
6
6 2 3 4 5 1
?LLRLL
8
1 7 5 6 2 8 4 3
?R??????
12
6 10 7 1 8 5 12 2 11 3 4 9
????????????
3
-1
-1
4
4
3
5
8
Note
In the first test case, there are two connected graphs (the labels are indices):
 |  |
The graph on the left has a diameter of $2$, while the graph on the right has a diameter of $3$, so the answer is $3$.
In the second test case, there are no connected graphs, so the answer is $-1$.