1. Bracket2019

Задача Bracket2019. Дана послідовність круглих дужок. За одну секунду ви можете поміняти місцями будь-які дві дужки. За який мінімальний час ви зможете отримати правильну послідовність дужок?  Дужковий вираз вважається правильним, якщо:

- він є порожнім

- якщо A та B правильні, то AB правильний

- якщо A правильний, то (A) правильний

Технічні умови. Програма Bracket2019 читає з пристрою стандартного введення послідовність дужок довжиною не більше 10⁶ символів і виводить на пристрій стандартного виведення шуканий час. Якщо отримати правильну послідовність дужок неможливо, програма повинна вивести -1.

Приклади.