Correct Parentheses

Interview

Time limit1sMemory limit1024 MB

Summary

Count how many single-character deletions from a bracket string leave a correct balanced parenthesis sequence.

Level: Medium6 of 10
Topics: String, Prefix sum, Greedy, Implementation
Solved: No attempts yet

Problem

For a string $S$ consisting of $\texttt{(}$ and $\texttt{)}$ , print the number of ways to delete exactly one parenthesis so that the result is a correct parenthesis sequence.

A correct parenthesis sequence is defined as follows.

$\texttt{()}$ is a correct parenthesis sequence.
If $\texttt{A}$ is a correct parenthesis sequence, then $\texttt{(A)}$ is a correct parenthesis sequence.
If $\texttt{A}$ and $\texttt{B}$ are correct parenthesis sequences, then $\texttt{AB}$ is a correct parenthesis sequence.

Input

The first line gives the string $S$ with no spaces. ( $3 \leq \vert S \vert \leq 100\,000$ , and $\vert S \vert$ is odd.)

The answer is at least $1$ . That is, at least one character exists whose deletion yields a correct parenthesis sequence.

Output

Print the number of ways to obtain a correct parenthesis sequence.

Examples2

Example 1
Input
```
()(()
```
Expected output
```
2
```
Example 2
Input
```
()(()))
```
Expected output
```
4
```