Problem description

Jasio znalazł w szufladzie ciąg nawiasów. Szybko obejrzał go z każdej strony i wydaje mu się, że nie jest to niestety poprawne nawiasowanie. Postanowił wybrać niektóre nawiasy z tego ciągu i wymazać je, aby pozostałe nawiasy tworzyły poprawne nawiasowanie.

Poprawne nawiasowania możemy zdefiniować rekurencyjnie w następujący sposób:

• ciąg pusty jest poprawnym nawiasowaniem,
• jeśli S i T są poprawnymi nawiasowaniami, to ich złączenie ST także jest poprawnym nawiasowaniem,
• jeśli S jest poprawnym nawiasowaniem to (S) też jest.

Oczywiście, Jasio chciałby napracować się jak najmniej i zmazać jak najmniejszą liczbę nawiasów. Pomóż mu!

Napisz program, który: wczyta nawiasy znalezione przez Jasia, wyznaczy minimalną liczbę nawiasów, które trzeba wymazać, aby uzyskać poprawne nawiasowanie i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się ciąg znaków ( oraz ) – ciąg nawiasów znaleziony przez Jasia.

Wyjście

Twój program powinien wypisać na wyjście jedną liczbę całkowitą – minimalną liczbę nawiasów, które należy zmazać, aby uzyskać poprawne nawiasowanie.

Uwaga

Pierwsze wrażenie Jasia co do niepoprawności nawiasowania mogło być mylne. Jeśli nawiasowanie podane na wejściu jest poprawne, wówczas poprawną odpowiedzią jest 0.

Ograniczenia

Długość ciągu nawiasów na wejściu nie przekracza 500 000 znaków.

Przykład

)(()()))(()

3