Is This a Give-Away?

msi1427 16th December Programming...
Limits 2s, 512 MB

Once there lived an ancient mage named Farabi. He could always give perfect weather forecast. He never revealed how. After he died no one could predict the weather perfectly anymore. In his lifetime, he wrote a book in an encrypted language. After so many years and so many trials, a brilliant coder named Masum broke the encryption.

After decryption, Masum found out the key to the weather forecast. Considering the waves of the rivers around, he can get a sequence consisting of curly braces ('{', '}'). The maximum depth that can be achieved after removing some or no curly braces, that means the depth of maximum nested curly bracket sequence that can be created, is the key to everything. Masum wants you to build a system for it while he finds out the sequence.

For example, in the bracket sequence "{{}}{}" The maximum depth is 2.

Input

Input contains a string ss (s105|s| \le 10^5) containing '{' and '}' only.

Output

Print one integer denoting the answer.

Sample

InputOutput
{{}{}{}}
3

In the given sample, if we remove the 3rd and 6th braces, we will get {{{}}} which will have a depth 3. There is no other way to get more than 3.


Submit

Login to submit.

Statistics

80% Solution Ratio
Mr_BangladeshEarliest, Dec '19
Circle.21Fastest, 0.0s
Circle.21Lightest, 131 kB
mdvirusShortest, 273B
Toph uses cookies. By continuing you agree to our Cookie Policy.