Maximum Valid Parentheses Prefix Length

You are given a parentheses string s. In one operation, you may swap any two adjacent characters. Since any permutation of the string can be obtained using adjacent swaps, you can reorder s arbitrarily. Your task is to determine the maximum length of a prefix that can be made valid (i.e. properly matched) by performing several such operations.

A valid parentheses string has the property that, when scanning from left to right, the number of ( is always greater than or equal to the number of ) and the total number of ( equals that of ) in the string. In the best scenario, you can pair up as many opening and closing brackets as possible.

Hint: If the string contains O opening and C closing brackets, then the maximum number of pairs is min(O, C). Thus, the maximum valid prefix length is 2 \(\times min(O, C)\).

inputFormat

The input consists of one line containing the string s, which is composed solely of the characters '(' and ')'.

outputFormat

Output a single integer - the maximum length of a valid prefix that can be formed by rearranging s using the allowed operations.

sample

(()

2