Longest Well-Formed Run

MediumStringStackDynamic-ProgrammingParentheses6 hidden tests

You are given a string of only the characters ( and ). A substring is well-formed if every opening bracket has a matching closing bracket and pairs are properly nested. Find the length of the longest contiguous well-formed substring.

Input format

A single line: a string of ( and ) characters (possibly empty).

Output format

A single integer: the length of the longest well-formed contiguous substring (0 if none).

Constraints

0 <= length of the string <= 100000

Examples

Example 1

Input

(()

Expected

Explanation

The longest well-formed substring is "()" (the last two characters), which has length 2.

Example 2

Input

)()())

Expected

Explanation

The substring "()()" in the middle is well-formed and has length 4; nothing longer works.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →