Minimum Operations to Balance Parentheses

You are given a string s consisting only of the characters '(' and ')'. A string is considered balanced if:

1. The number of opening parentheses '(' equals the number of closing parentheses ')'.

2. For every prefix of the string, the number of '(' is no less than the number of ')'.

Your task is to determine the minimum number of insertions required to transform s into a balanced string. Formally, if we denote the number of insertions needed as operations, then you must compute:

\( \text{operations} = \text{left_needed} + \text{right_needed} \)

where left_needed is the number of '(' needed and right_needed is the number of ')' needed to balance the string.

Example:

• Input: (()))( → Output: 2
• Input: )( → Output: 2
• Input: ((( → Output: 3

inputFormat

The input consists of a single line containing the string s (with \(1 \leq |s| \leq 10^5\)), which is composed solely of the characters '(' and ')'.

outputFormat

Output a single integer representing the minimum number of insertions required to make the string balanced.

## sample

()

0