Codeforces Round #529 (Div.3)- Bài 5

Bài 5: You are given a bracket sequences $s$ consisting of $n$ opening '(' ans closing ')' brackets.
A regular 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 "( ) ( )","( ( ) ) " are regular (the resulting expressions are "( 1 )+ ( 1 )","( (1+1)+1)", and ") (" and "(" are not.

You can change the type of some bracket $s_i$. It means that if $s_i= ' ) '$ then you can change it to '(' and vice versa.
Your task is to calculate the number of position $i$ such that if you change the type of the $i-th$ bracket, then the resulting bracket sequence becomes regular.
Input
The first line of the input contains one integer $n(1\le n\le 10^6)$- the length of the bracket sequence.
The second line of the input contains the string $s$ consisting of $n$ opening '(' and closing ')' brackets.
Output
Print one integer- the number of position $i$ such that if you change the type of the $i-th$ bracket, then the resulting bracket sequence becomes regular.

Examples

input

Copy

6
(((())

output

Copy

3

input

Copy

6
()()()

output

Copy

0

input

Copy

1
)

output

Copy

0

input

Copy

8
)))(((((

output

Copy

0

Solution:

#include <iostream>

using namespace std;

const int N = 1e6 + 6;

int n, ans;
char s[N];
int a[N], m[N];

int main() {
 cin >> n >> s + 1;
 for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + (s[i] == '(') - (s[i] == ')');
 for (int i = n; i >= 1; --i) m[i] = min(i == n ? N : m[i + 1], a[i]);
 for (int i = 1; i <= n && a[i - 1] >= 0; ++i) {
  int d = ((s[i] == '(') - (s[i] == ')')) * 2;
  ans += m[i] >= d && a[n] == d;
 }
 cout << ans << endl;
 return 0;
}