codeforces 918C The Monster

As Will is stuck in the Upside Down, he can still communicate with his mom, Joyce, through the Christmas lights (he can turn them on and off with his mind). He can't directly tell his mom where he is, because the monster that took him to the Upside Down will know and relocate him.

$\text{[math]}$

Thus, he came up with a puzzle to tell his mom his coordinates. His coordinates are the answer to the following problem.

A string consisting only of parentheses ('(' and ')') is called a bracket sequence. Some bracket sequence are called correct bracket sequences. More formally:

Empty string is a correct bracket sequence.
if s is a correct bracket sequence, then (s) is also a correct bracket sequence.
if s and t are correct bracket sequences, then st (concatenation of s and t) is also a correct bracket sequence.

A string consisting of parentheses and question marks ('?') is called pretty if and only if there's a way to replace each question mark with either '(' or ')' such that the resulting string is a non-empty correct bracket sequence.

Will gave his mom a string s consisting of parentheses and question marks (using Morse code through the lights) and his coordinates are the number of pairs of integers (l, r) such that 1 ≤ l ≤ r ≤ |s| and the string slsl + 1... sr is pretty, where si is i-th character of s.

Joyce doesn't know anything about bracket sequences, so she asked for your help.

Input

The first and only line of input contains string s, consisting only of characters '(', ')' and '?' (2 ≤ |s| ≤ 5000).

Output

Print the answer to Will's puzzle in the first and only line of output.

Examples

input

((?))

output

input

??()??

output

Note

For the first sample testcase, the pretty substrings of s are:

"(?" which can be transformed to "()".
"?)" which can be transformed to "()".
"((?)" which can be transformed to "(())".
"(?))" which can be transformed to "(())".

For the second sample testcase, the pretty substrings of s are:

"??" which can be transformed to "()".
"()".
"??()" which can be transformed to "()()".
"?()?" which can be transformed to "(())".
"??" which can be transformed to "()".
"()??" which can be transformed to "()()".
"??()??" which can be transformed to "()()()".

大意：

给一个括号和问号组成的序列，问号可以视为左括号或右括号。问共有多少个合法（左右括号匹配，具体规则详见题意）的区间数（不是方案数）。

题解：

直觉是用栈，然而实际上用不到栈。

O(N^2)的复杂度是可以解决问题的。

枚举区间左端点，从每个左端点尽量向右延伸，在延伸的过程中统计合法区间数。

那么问题就在于如何判断当前区间是否合法：

策略：在延伸的过程中统计'('的数量，如果碰到‘?’，也记录下来，并将'?'暂时看为')'，如果碰到右括号且左括号数量不够时，将一个'?'变为左括号。

当然，如果'('和'?'数量相等时碰到'?'，直接看成'('。因为这种情况下，前面的'?'必须都看做')'。

维护两个变量 L和 off。L代表左括号的数量，off代表被看为')'的'?'数量。

当前序列长度为偶数时，答案+1即可。

 1 /*
 2 Welcome Hacking
 3 Wish You High Rating
 4 */
 5 #include<iostream>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<ctime>
 9 #include<cstdlib>
10 #include<algorithm>
11 #include<cmath>
12 #include<string>
13 using namespace std;
14 int read(){
15     int xx=0,ff=1;char ch=getchar();
16     while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
17     while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
18     return xx*ff;
19 }
20 int len,ans;
21 char s[5010];
22 int main(){
23     //freopen("in","r",stdin);
24     gets(s+1);
25     len=strlen(s+1);
26     for(int i=1;i<len;i++){
27         int L=0,off=0;
28         for(int j=i;j<=len;j++){
29             if(s[j]=='(')
30                 L++;
31             else if(s[j]=='?'){
32                 if(L==off)
33                     L++;
34                 else
35                     off++;
36             }
37             else{
38                 if(L==off)
39                     off--;
40                 else
41                     L--;
42                 if(L<0)
43                     break;
44                 if(off<0)
45                     break;
46             }
47             if((j-i+1)%2==0&&off==L)
48                 ans++;
49         }
50     }
51     printf("%d
",ans);
52     return 0;
53 }

View Code