Это простая версия задачи. Разница между простой и сложной версиями задачи заключается только в допустимых символах в \(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\), если невозможно получить ни один связный граф.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальный диаметр среди всех связных графов, которые вы можете получить, или \(-1\), если таковых нет.
Примечание
Для первого набора входных данных ниже показаны примеры некоторых графов, которые можно получить (в вершинах написаны индексы):
Во втором наборе входных данных у единственного связного графа диаметр равен \(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
|