Minimum Parentheses Insertion to Balance Parentheses

You are given a string consisting solely of the characters '(' and ')'. However, the parentheses in the string are not guaranteed to be paired. To improve the appearance of the string, your task is to insert the fewest number of parentheses (you may insert them at any position and as many as required, but you cannot modify the existing ones) such that the resulting string becomes balanced.

A string is considered balanced if every opening parenthesis '(' has a corresponding closing parenthesis ')' in the correct order. Formally, a string is balanced if it can be transformed into a valid parentheses sequence.

inputFormat

The input consists of a single line that contains a non-empty string S composed only of the characters '(' and ')'. The length of S does not exceed 10⁵.

outputFormat

Output a single integer denoting the minimum number of parentheses that need to be inserted into the string to make it balanced.

sample

()(

1