Задача . A. Интересные конкурсы

Напомним, что скобочная последовательность называется правильной, если путем вставки в неё символов «+» и «1» можно получить из неё корректное математическое выражение. Например, последовательности «(())()», «()» и «(()(()))» — правильные, в то время как «)(», «(()» и «(()))(» — нет.

Учительница дала классу, в котором учится Дмитрий, очень странное задание — она попросила каждого из учеников придумать последовательность произвольной длины, состоящую только из открывающих и закрывающих скобок. После этого все ученики по очереди называли придуманные ими последовательности. Когда очередь дошла до Димы, он внезапно понял, что у всех его одноклассников получились правильные скобочные последовательности, а получилась ли у него правильная скобочная последовательность, он не знал.

Дима подозревает, что он просто прослушал слово «правильная» в постановке задания, поэтому хочет срочно исправить ситуацию — для этого он решил немного изменить свою последовательность. А именно, он решил произвольное число раз (возможно, нулевое) выполнить операцию перемешивания.

Для выполнения одной операции перемешивания Дима выбирает произвольный подотрезок (подстроку) последовательности и произвольным образом переставляет все символы на нём. Такая операция занимает ровно \(l\) наносекунд, где \(l\) — длина подотрезка, который Дима выбрал для перемешивания. Легко заметить, что при этом число открывающих скобок не меняется, равно как и число закрывающих. Например, для «))((» он может выбрать подотрезок «)(» и перемешать символы в нём, получив «)()(» (эта операция потребует \(2\) наносекунды).

Уже совсем скоро подойдёт очередь Димы называть свою последовательность, поэтому он обратился за помощью к вам. Помогите ему определить минимальное время, за которое он может сделать свою последовательность правильной, или определите, что сделать это невозможно.