Latam++

Time limit0.5sMemory limit1024 MB

Summary

Count the substrings of a string made of lowercase letters, parentheses, and the operators + - * / that are valid arithmetic expressions.

Level: Medium7 of 10
Topics: Stack, Prefix sum
Solved: No attempts yet

Problem

The world does not have enough programming languages yet. To help with that, the Internal Committee for the Perfection of C (ICPC) is planning to build a brand new programming language: Latam++.

In Latam++, a variable name consists exclusively of one or more lowercase letters of the English alphabet. A valid expression is a "well-formed" string, expressing how to combine variables by using the four arithmetic binary operators "+", "-", "*" and "/", possibly with parentheses.

Formally, valid expressions are exactly those strings that can be produced by the following rules.

A variable name is a valid expression.
Surrounding any valid expression in parentheses produces another valid expression.
If A and B are valid expressions, then the concatenation AcB is a valid expression, where c is any of the four arithmetic binary operators "+", "-", "*" and "/".

Thus, the following are all valid expressions:

a+b
a+b*(c+b)
atoms+boots*(charly+bob)
(((a)))*(bbasdsaqwe/a/a/a)

On the contrary, the following are not valid expressions:

a+
a+b(c+b)
atoms+boots*((charly+bob)
((()))*(bbasdsaqwe/a/a/a)

The language is far from complete. It will likely take ICPC decades of debate before the first version of Latam++ is released. Meanwhile, this problem focuses on one feature of its compiler, Automatic Valid Substring Expression Counting (AVSEC).

AVSEC is a compiler feature that reports the total number of substrings of a given string that are valid expressions. Your task is to implement AVSEC.

For counting purposes, two substrings are considered different if they start or end at different indexes, even if the corresponding strings are identical (that is, they are the same sequence of characters).

Input

The input consists of a single line that contains a string $S$ ( $1 \le |S| \le 2 \times 10^5$ ), which is made up of lowercase letters, opening or closing parentheses, and the four characters "+", "-", "*" and "/".

Output

Output a single line with an integer indicating the number of substrings of $S$ that are valid expressions.

Examples3

Example 1
Input
```
a+b(c+b)
```
Expected output
```
7
```
Example 2
Input
```
aa
```
Expected output
```
3
```
Example 3
Input
```
a-a
```
Expected output
```
3
```