Bessie tenta digitar uma string de parênteses balanceada no novo laptop, mas seus grandes cascos a tornam desajeitada e ela erra. Encontre o mínimo de caracteres a inverter (abrir para fechar ou vice-versa) para balancear a string.

Há várias definições de balanceamento. A mais simples exige o mesmo total de parênteses de abertura e fechamento, e pelo menos tantos de abertura quanto de fechamento em qualquer prefixo. Estas strings são balanceadas:

()
(())
()(()())

Estas não são:

)(
())(
((())))

Entrada

• Linha 1: uma string de parênteses $A$ de comprimento par, com no máximo 100,000 caracteres.

Saída

• Linha 1: um inteiro, o mínimo número de parênteses a inverter para balancear a string.

Exemplos

Entrada 1

())(

Saída 1

2

Explicação

É preciso inverter o último parêntese e um dos dois de fechamento do meio.

Autor: Brian Dean, 2012