Length of Longest Balanced Subsequence

Given a string s containing brackets "(" and ")", return the length of the longest subsequence of balanced brackets.

Constraints

• n ≤ 100,000 where n is length of s.

https://binarysearch.com/problems/Length-of-Longest-Balanced-Subsequence

Examples

Example 1

Input

• s = ())(()

Output

• answer = 4

Explanation

We can take the subsequence "()()"

Example 2

Input

• s = ))()))()

Output

• answer = 4

Explanation

We can take the subsequence “()()”. Note that characters in the subsequence do not have to be contiguous.

Example 3

Input

• s = ))((

Output

• answer = 0

Explanation

We can’t take any letters from s that’s balanced, so the longest balanced subsequence is “” (empty string).

Example 4

Input

• s = ((((())

Output

• answer = 4

Explanation

We can make the subsequence (()).

Solution