Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Not As Hard As It Seems

By Amateur · Limits 1s, 512 MB

Sakib and Shamim are good friends. As Sakib is a little naughty, every night before exam he disturbs Shamim. One day Shamim got an idea to get rid of Sakib. Shamim gave him a sequence of parentheses and brackets, and told him to determine the maximum length of a valid subsequence.

For example, [] , ([]) are valid subsequences but (], [)(] are not. Remember an empty sequence is also a valid subsequence.

Since Sakib was intelligent he solved the problem easily and continued disturbing Shamim. Can you solve it too?

Input

You will be given multiple strings of parentheses and brackets, one in each line. The length of each string will be no more than 106.

Output

For each such string, you will have to determine the maximum length of valid subsequence.

Sample

InputOutput
[]()
([])()
2
4

The valid subsequences of maximum length for the first string are [] or (). For the second string it is ([]).


Discussion

Statistics


45% Solution Ratio

Fazlerabbi.Earliest, 3M ago

Fazlerabbi.Fastest, 0.0s

Fazlerabbi.Lightest, 0 B

Fazlerabbi.Shortest, 778B

Submit

Login to submit

Related Contests