codeforces#P1987G1. Spinning Round (Easy Version)
Spinning Round (Easy Version)
Description
This is the easy version of the problem. The only difference between the two versions are the allowed characters in $s$. In the easy version, $s$ only contains the character ?. 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$, consisting only of the character ?.
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$^{\text{∗}}$ over all connected 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 character ?.
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 character ?.
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
?????
2
1 2
??
3
3 1 2
???
7
5 3 1 6 4 2 7
???????
5
5 2 1 3 4
?????
6
6 2 3 4 5 1
??????
8
1 7 5 6 2 8 4 3
????????
12
6 10 7 1 8 5 12 2 11 3 4 9
????????????
4
1
2
6
4
5
5
8
Note
In the first test case, here are some possible connected graphs that you can form (the labels are indices):
 |  |  |
In the second test case, the only connected graph has a diameter of $1$.