SOLVE

LATER

Bracket sequences

/

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\)

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

Initializing Code Editor...