这是问题的简单版本。两个版本之间的唯一区别是 $$$s$$$ 中允许的字符。在简单版本中,$$$s$$$ 仅包含字符 ?。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
给你一个长度为 $$$n$$$ 的排列 $$$p$$$。您还会获得一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符 ?。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$:
- 将 $$$l_i$$$ 定义为最大索引 $$$j < i$$$,使得 $$$p_j > p_i$$$。如果没有这样的索引,$$$l_i := i$$$。
- 将$$$r_i$$$定义为最小索引$$$j > i$$$,使得$$$p_j > p_i$$$。如果没有这样的索引,$$$r_i := i$$$。
最初,您有一个无向图,其中有 $$$n$$$ 个顶点(编号从 $$$1$$$ 到 $$$n$$$)且没有边。然后,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,向图中添加一条边:
- 如果 $$$s_i =$$$ L,则将边 $$$(i, l_i)$$$ 添加到图形中。
- 如果 $$$s_i =$$$ R,则将边 $$$(i, r_i)$$$ 添加到图形中。
- 如果 $$$s_i =$$$ ?,则根据您的选择将边 $$$(i, l_i)$$$ 或边 $$$(i, r_i)$$$ 添加到图表中。
找出您可以形成的所有连通图的最大可能直径$$$^{\text{*}}$$$。如果无法形成任何连通图,则输出 $$$-1$$$。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$) — 排列 $$$p$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — $$$p$$$ 的元素,保证形成排列。
每个测试用例的第三行包含一个长度为$$$n$$$的字符串$$$s$$$。保证它仅由字符 ? 组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$4 \cdot 10^5$$$。
输出
对于每个测试用例,输出您形成的所有连通图的最大可能直径,如果无法形成任何连通图,则输出 $$$-1$$$。
示例
输入 #1
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 ????????????
输出 #1
4 1 2 6 4 5 5 8
注意
在第一个测试用例中,以下是您可以形成的一些可能的连通图(标签是索引):
在第二个测试用例中,唯一连通图的直径为 $$$1$$$。