Problem 1 (Array) A bracket sequence is a string that contains only characters' (' and ')'. A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters 'l' and '+' between the original characters of the sequence. For example, bracket sequences' () ()' and '(0)' are correct. The resulting expressions of these sequences are: '(1)+(1)' and '((1+1)+1)'. However, '(',') (', and '(' are incorrect bracket sequences. You are given a bracket sequence s (5152...S.), where s; denotes the type of its bracket (open or close). It is not mandatory that s is necessarily correct. Your task is to determine the number of i's such that siSit1... SnS1S2...Si-1 is a correct bracket sequence. Input format The single line contains sequence s. Output format Print the number of shifts denoting the correct bracket sequence. Constraints Is 55x105 Sample Input ) 000 Sample Output 3