404038: GYM101401 B Smiley Faces (B)

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Smiley Faces (B)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Mr. Light now have a string that consists only of the three characters: ':', '(', and ')'.

Mr. Light considers a colon ‘:’ followed by a closing bracket ')' as a smiley face. So ":)" is a smiley face while "(:" is not. Now he wants to choose exactly one prefix (one or more characters at the beginning) of this string and mirror it (reverse it and flip the brackets).

For example, the string ":):((" mirrored is ")):(:".

What is the maximum number of smiley faces Mr. Light can get in the string after mirroring exactly one prefix?

Input

The input contains a non-empty string of no more than 2 × 105 characters. Each character is either ':', '(', or ')'.

Output

Print the maximum number of smiley faces Mr. Light can get after mirroring exactly one prefix.

ExamplesInput
:(:):(:):)
Output
4
Input
:)::(:(:
Output
2

加入题单

上一题 下一题 算法标签: