Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

E. Elimination Bracket
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$t$$$ be a string of '(' and ')'. The beauty of such a string is the length of its longest subsequence (not necessarily contiguous) that is correctly parenthesised. A string $$$a$$$ is a subsequence of the string $$$t$$$ if $$$a$$$ can be obtained from $$$t$$$ by the deletion of several (possibly, zero or all) characters. A string is considered to be correctly parenthesised if it satisfies the following conditions:

  • The string consists solely of the characters '(' and ')'.
  • The number of opening parentheses '(' is equal to the number of closing parentheses ')'.
  • For every prefix of the string, the number of opening parentheses is greater than or equal to the number of closing parentheses.

You are given a string $$$s$$$ consisting of characters '(', ')' and '?'. Replace each '?' by either '(' or ')' such that the beauty of the resulting string $$$t$$$ is minimized.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 4 \cdot 10^6$$$) — the length of the input string.

The second line contains the string $$$s$$$ of length $$$n$$$. $$$s$$$ consists of only characters '(', ')' and '?'.

Output

Output the minimum possible beauty.

Examples
Input
10
(((??)))))
Output
6
Input
22
()??)((?)?)()()?)??)?)
Output
10
Note

In the first example, there are four ways of substituting the '?':

  • ((((()))))
  • (((())))))
  • ((()()))))
  • ((()))))))

The beauty of these strings is $$$10$$$, $$$8$$$, $$$8$$$, and $$$6$$$, respectively.