Олимпиадный тренинг

Задача . G1. Очень круглый спин (простая версия)

Задача

Темы: Деревья дп разделяй и властвуй *2900

Это простая версия задачи. Разница между простой и сложной версиями задачи заключается только в допустимых символах в $s$. В простой версии строка $s$ содержит только символ ?. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Дана перестановка $p$ длины $n$. Также дана строка $s$ длины $n$, содержащая только символ ?.

Для каждого $i$ от $1$ до $n$:

Определим $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$) и без рёбер. Затем для каждого $i$ от $1$ до $n$ в граф добавляется одно ребро:

Если $s_i =$ L, в граф добавляется ребро $(i, l_i)$.
Если $s_i =$ R, в граф добавляется ребро $(i, r_i)$.
Если $s_i =$ ?, в граф добавляется либо ребро $(i, l_i)$, либо ребро $(i, r_i)$ по вашему выбору.

Найдите максимально возможный диаметр$^{\text{∗}}$ среди всех связных графов, которые вы можете получить. Выведите $-1$, если невозможно получить ни один связный граф.

$^{\text{∗}}$ Пусть $d(s, t)$ это наименьшее возможное число рёбер на пути от $s$ до $t$.

Диаметр графа определяется как наибольшее значение $d(s, t)$ по всем парам вершин $s$ и $t$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $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$, которые гарантированно являются перестановкой.

Третья строка каждого набора входных данных содержит строку $s$ длины $n$. Гарантируется, что строка содержит только символы ?.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $4 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальный диаметр среди всех связных графов, которые вы можете получить, или $-1$, если таковых нет.

Примечание

Для первого набора входных данных ниже показаны примеры некоторых графов, которые можно получить (в вершинах написаны индексы):

$\text{[math]}$

Во втором наборе входных данных у единственного связного графа диаметр равен $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 ????????????	4 1 2 6 4 5 5 8

time 7000 ms
memory 1024 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет