Problem Description

Candela is a cartoonist. She has a strange hobby: drawing brackets on paper. One day, right after getting up, Candela drew a sequence of brackets in a row, containing parentheses () , square brackets [] , and curly braces {} , with total length $N$. This randomly drawn bracket sequence looks messy, so Candela defines what kinds of bracket sequences are “beautiful”:

1. The empty bracket sequence is beautiful.
2. If bracket sequence $A$ is beautiful, then (A) , [A] , and {A} are also beautiful.
3. If bracket sequences $A$ and $B$ are both beautiful, then AB is also beautiful.

For example, [(){}]() is a beautiful bracket sequence, while )({)[}]( is not.

Now Candela wants to find a continuous segment in the bracket sequence she drew such that this substring is beautiful and its length is as large as possible. Can you help her?

Input Format

The first line contains a bracket sequence of length $N$.

Output Format

Output one integer, the length of the longest beautiful continuous substring.

({({(({()}})}{())})})[){{{([)()((()]]}])[{)]}{[}{)

4

Hint

Constraints: the testdata guarantees $5 \leq N \leq 10^4$. The values of $N$ in each test point are: $5, 10, 50, 100, 100, 1000, 1000, 10000, 10000, 10000$.

Translated by ChatGPT 5