{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eA bracketed sequence is called correct (regular) if by inserting \"+\" and \"1\" you can get a well-formed mathematical expression from it. For example, sequences \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(())()\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(()(()))\u003c/span\u003e\" are correct, while \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)(\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(()\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(()))(\u003c/span\u003e\" are not.\u003c/p\u003e\u003cp\u003eThe teacher gave Dmitry\u0027s class a very strange task\u0026nbsp;— she asked every student to come up with a sequence of arbitrary length, consisting only of opening and closing brackets. After that all the students took turns naming the sequences they had invented. When Dima\u0027s turn came, he suddenly realized that all his classmates got the correct bracketed sequence, and whether he got the correct bracketed sequence, he did not know.\u003c/p\u003e\u003cp\u003eDima suspects now that he simply missed the word \"correct\" in the task statement, so now he wants to save the situation by modifying his sequence slightly. More precisely, he can \u003cspan class\u003d\"tex-font-style-bf\"\u003ethe arbitrary number of times\u003c/span\u003e (possibly zero) perform the \u003cspan class\u003d\"tex-font-style-it\"\u003ereorder\u003c/span\u003e operation.\u003c/p\u003e\u003cp\u003eThe reorder operation consists of choosing an arbitrary consecutive subsegment (substring) of the sequence and then reordering all the characters in it in an arbitrary way. Such operation takes $$$l$$$ nanoseconds, where $$$l$$$ is the length of the subsegment being reordered. It\u0027s easy to see that reorder operation doesn\u0027t change the number of opening and closing brackets. For example for \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e))((\u003c/span\u003e\" he can choose the substring \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)(\u003c/span\u003e\" and do reorder \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)()(\u003c/span\u003e\" (this operation will take $$$2$$$ nanoseconds).\u003c/p\u003e\u003cp\u003eSince Dima will soon have to answer, he wants to make his sequence correct as fast as possible. Help him to do this, or determine that it\u0027s impossible.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$n$$$ ($$$1 \\le n \\le 10^6$$$)\u0026nbsp;— the length of Dima\u0027s sequence.\u003c/p\u003e\u003cp\u003eThe second line contains string of length $$$n$$$, consisting of characters \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e\" only.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer\u0026nbsp;— the minimum number of nanoseconds to make the sequence correct or \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e\" if it is impossible to do so.\u003c/p\u003e"}},{"title":"Examples","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\u003e8\n))((())(\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e3\n(()\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example we can firstly reorder the segment from first to the fourth character, replacing it with \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()()\u003c/span\u003e\", the whole sequence will be \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()()())(\u003c/span\u003e\". And then reorder the segment from the seventh to eighth character, replacing it with \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e\". In the end the sequence will be \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()()()()\u003c/span\u003e\", while the total time spent is $$$4 + 2 \u003d 6$$$ nanoseconds.\u003c/p\u003e"}}]}