26B.md (968B)
1 Source: https://codeforces.com/problemset/problem/26/B 2 3 B. Regular Bracket Sequence 4 5 time limit per test 6 7 5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters «+» and «1» into this sequence. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not. 22 23 One day Johnny got bracket sequence. He decided to remove some of the brackets from it in order to obtain a regular bracket sequence. What is the maximum length of a regular bracket sequence which can be obtained? 24 25 Input 26 27 Input consists of a single line with non-empty string of «(» and «)» characters. Its length does not exceed 106. 28 29 Output 30 31 Output the maximum possible length of a regular bracket sequence. 32 33 Examples 34 35 Input 36 37 ``` 38 (()))( 39 ``` 40 41 Output 42 43 ``` 44 4 45 ``` 46 47 Input 48 49 ``` 50 ((()()) 51 ``` 52 53 Output 54 55 ``` 56 6 57 ```