Bracket sequences
/

## 1-D array, Arrays, Data Structures

Problem
Editorial
Analytics

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 '1' and '+' between the original characters of the sequence. For example, bracket sequences '()()' and '(())' 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(s_1 s_2 ... s_n)$, where $s_i$ denotes the type of $i$'s 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 $s_i s_{i+1} ... s_n s_1 s_2 ... s_{i-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

$|s| \le 5\times 10^5$

SAMPLE INPUT
)()()(
SAMPLE OUTPUT
3
Explanation

For all $i=2,4,6$, shift of string will be ()()(), which is correct bracket sequence. Since, answer is 3

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...