{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eWe give the following inductive definition of a “regular brackets” sequence:\u003c/p\u003e\u003cul\u003e\u003cli\u003ethe empty sequence is a regular brackets sequence,\u003c/li\u003e\u003cli\u003eif \u003ci\u003es\u003c/i\u003e is a regular brackets sequence, then (\u003ci\u003es\u003c/i\u003e) and [\u003ci\u003es\u003c/i\u003e] are regular brackets sequences, and\u003c/li\u003e\u003cli\u003eif \u003ci\u003ea\u003c/i\u003e and \u003ci\u003eb\u003c/i\u003e are regular brackets sequences, then \u003ci\u003eab\u003c/i\u003e is a regular brackets sequence.\u003c/li\u003e\u003cli\u003eno other sequence is a regular brackets sequence\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eFor instance, all of the following character sequences are regular brackets sequences:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ccode\u003e(), [], (()), ()[], ()[()]\u003c/code\u003e\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003ewhile the following character sequences are not:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ccode\u003e(, ], )(, ([)], ([(]\u003c/code\u003e\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003eGiven a brackets sequence of characters \u003ci\u003ea\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\u003ci\u003ea\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e … \u003ci\u003ea\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e, your goal is to find the length of the longest regular brackets sequence that is a subsequence of \u003ci\u003es\u003c/i\u003e. That is, you wish to find the largest \u003ci\u003em\u003c/i\u003e such that for indices \u003ci\u003ei\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003ei\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, …, \u003ci\u003ei\u003csub\u003em\u003c/sub\u003e\u003c/i\u003e where 1 ≤ \u003ci\u003ei\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u0026lt; \u003ci\u003ei\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e \u0026lt; … \u0026lt; \u003ci\u003ei\u003csub\u003em\u003c/sub\u003e\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003cspan style\u003d\"vertical-align: sub\"\u003e\u003cfont size\u003d\"1\"\u003e1\u003c/font\u003e\u003c/span\u003e\u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u003cspan style\u003d\"vertical-align: sub\"\u003e\u003cfont size\u003d\"1\"\u003e2\u003c/font\u003e\u003c/span\u003e … \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003cspan style\u003d\"vertical-align: sub\"\u003e\u003cfont size\u003d\"1\"\u003em\u003c/font\u003e\u003c/span\u003e\u003c/i\u003e is a regular brackets sequence.\u003c/p\u003e\u003cp\u003eGiven the initial sequence \u003ccode\u003e([([]])]\u003c/code\u003e, the longest regular brackets subsequence is \u003ccode\u003e[([])]\u003c/code\u003e.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters \u003ccode\u003e(\u003c/code\u003e, \u003ccode\u003e)\u003c/code\u003e, \u003ccode\u003e[\u003c/code\u003e, and \u003ccode\u003e]\u003c/code\u003e; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e((()))\r\n()()()\r\n([]])\r\n)[)(\r\n([][][)\r\nend\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\r\n6\r\n4\r\n0\r\n6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}