Задача №114745. Интересные конкурсы
Учительница дала классу, в котором учится Дмитрий, очень странное задание — она попросила каждого из учеников придумать последовательность произвольной длины, состоящую только из открывающих и закрывающих скобок. После этого все ученики по очереди называли придуманные ими последовательности. Когда очередь дошла до Димы, он внезапно понял, что у всех его одноклассников получились правильные скобочные последовательности, а получилась ли у него правильная скобочная последовательность, он не знал.
Дима подозревает, что он просто прослушал слово «правильная» в постановке задания, поэтому хочет срочно исправить ситуацию — для этого он решил немного изменить свою последовательность. А именно, он решил произвольное число раз (возможно, нулевое) выполнить операцию перемешивания . Для выполнения одной операции перемешивания Дима выбирает произвольный подотрезок последовательности и произвольным образом переставляет все символы на нём. Такая операция занимает ровно \(l\) наносекунд, где \(l\) — длина подотрезка, который Дима выбрал для перемешивания. Легко заметить, что при этом число открывающих скобок не меняется, равно как и число закрывающих.
Уже совсем скоро подойдёт очередь Димы называть свою последовательность, поэтому он обратился за помощью к вам. Помогите ему определить минимальное время, за которое он может сделать свою последовательность правильной, или определите, что сделать это невозможно.
В первой строке содержится одно целое число \(n\) (\(1 \le n \le 10^6\)) — длина последовательности Димы.
Вторая строка содержит строку длины \(n\), состоящую только из символов « ( » и « ) ».
Выведите единственное число — минимальное количество наносекунд, необходимое, чтобы сделать последовательность правильной, или « -1 », если сделать последовательность правильной с помощью операций перемешивания невозможно.
Напомним, что скобочная последовательность называется правильной, если путем вставки в неё символов «+» и «1» можно получить из неё корректное математическое выражение. Например, последовательности « (())() », « () » и « (()(())) » — правильные, в то время как « )( », « (() » и « (()))( » — нет.
В первом примере можно сначала перемешать подотрезок с первого по четвёртый символ, заменив его на « ()() » — получится последовательность « ()()())( », а затем перемешать подотрезок с седьмого по восьмой символ, заменив его на « () ». В итоге получится правильная скобочная последовательность « ()()()() », такие действия займут суммарно \(4 + 2 = 6\) наносекунд.
Тесты к этой задаче состоят из двух групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
| Дополнительные ограничения | |||
| Группа | Баллы | \(n\) | Комментарий |
| 0 | 0 | – | Тесты из условия. |
| 1 | 50 | \(n \le 1000\) | |
| 2 | 50 | – |
8 ))((())(
6
3 (()
-1