Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Examples

Example 1

Input:  s = "(()"
Output: 2

The longest valid parentheses substring is "()"

Example 2

Input:  s = ")()())"
Output: 4

The longest valid parentheses substring is "()()"

Example 3

Input:  s = ""
Output: 0

Example 4

Input:  s = "()(())"
Output: 6

The entire string is valid

Constraints

• 0 <= s.length <= 3 * 10^4
• s[i] is '(' or ')'