{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eMonocarp 有一个长度为 $$$n$$$ 的常规括号序列 $$$s$$$ ($$$n$$$ 是偶数)。他甚至想出了自己计算其成本的方法。\u003c/p\u003e\u003cp\u003e他知道在一个常规括号序列 (RBS) 中,每个开括号都与相应的闭括号配对。因此,他决定将 RBS 的 \u003cspan class\u003d\"tex-font-style-it\"\u003e成本\u003c/span\u003e 计算为相应括号对之间距离的总和。\u003c/p\u003e\u003cp\u003e例如,让我们看看 RBS \u003cspan class\u003d\"tex-font-style-tt\"\u003e(())()\u003c/span\u003e。它有三个括号对:\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e(__)__\u003c/span\u003e:位置 $$$1$$$ 和 $$$4$$$ 的括号之间的距离是 $$$4 - 1 \u003d 3$$$;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e_()___\u003c/span\u003e:距离是 $$$3 - 2 \u003d 1$$$;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e____()\u003c/span\u003e:距离是 $$$6 - 5 \u003d 1$$$。\u003c/li\u003e\u003c/ul\u003e 所以 \u003cspan class\u003d\"tex-font-style-tt\"\u003e(())()\u003c/span\u003e 的成本是 $$$3 + 1 + 1 \u003d 5$$$。\u003cp\u003e不幸的是,由于数据损坏,Monocarp 丢失了所有奇数位置的字符 $$$s_1, s_3, \\dots, s_{n-1}$$$。只有偶数位置的字符 ($$$s_2, s_4, \\dots, s_{n}$$$) 保留。例如,\u003cspan class\u003d\"tex-font-style-tt\"\u003e(())()\u003c/span\u003e 变成了 \u003cspan class\u003d\"tex-font-style-tt\"\u003e_(_)_)\u003c/span\u003e。\u003c/p\u003e\u003cp\u003eMonocarp 想通过在奇数位置放置括号来恢复他的 RBS。但由于恢复的 RBS 可能不唯一,他想选择一个具有 \u003cspan class\u003d\"tex-font-style-bf\"\u003e最小成本\u003c/span\u003e 的。对于 Monocarp 来说,这太难了,所以你能帮他吗?\u003c/p\u003e\u003cp\u003e提醒:一个 \u003cspan class\u003d\"tex-font-style-it\"\u003e常规括号序列\u003c/span\u003e 是一个仅由括号组成的字符串,该序列在插入 \u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e 和 \u003cspan class\u003d\"tex-font-style-tt\"\u003e+\u003c/span\u003e 后,形成一个有效的数学表达式。例如,\u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e、\u003cspan class\u003d\"tex-font-style-tt\"\u003e(())\u003c/span\u003e 或 \u003cspan class\u003d\"tex-font-style-tt\"\u003e(()())()\u003c/span\u003e 是 RBS,而 \u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e、\u003cspan class\u003d\"tex-font-style-tt\"\u003e()(\u003c/span\u003e 或 \u003cspan class\u003d\"tex-font-style-tt\"\u003e())(()\u003c/span\u003e 不是。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数 $$$t$$$ ($$$1 \\le t \\le 5000$$$)\u0026nbsp;— 测试用例的数量。接下来 $$$t$$$ 个案例随之而来。\u003c/p\u003e\u003cp\u003e每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \\le n \\le 2 \\cdot 10^5$$$; $$$n$$$ 是偶数)\u0026nbsp;— 字符串 $$$s$$$ 的长度。\u003c/p\u003e\u003cp\u003e每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,其中所有奇数位置的字符为 \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e_\u003c/span\u003e\u0027,所有偶数位置的字符为 \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e(\u003c/span\u003e\u0027 或 \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e)\u003c/span\u003e\u0027。\u003c/p\u003e\u003cp\u003e附加约束:\u003c/p\u003e\u003cul\u003e \u003cli\u003e$$$s$$$ 至少可以恢复为一个常规括号序列;\u003c/li\u003e\u003cli\u003e所有测试用例的 $$$n$$$ 的总和不超过 $$$2 \\cdot 10^5$$$。\u003c/li\u003e\u003c/ul\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,打印一个整数\u0026nbsp;— 从 $$$s$$$ 替换 \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e_\u003c/span\u003e\u0027 为括号后可以获得的常规括号序列的最小成本。\u003c/p\u003e"}},{"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\u003e4\n6\n_(_)_)\n2\n_)\n8\n_)_)_)_)\n8\n_(_)_(_)\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1\n4\n8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个测试用例中,最优选择是将 $$$s$$$ 设为 \u003cspan class\u003d\"tex-font-style-tt\"\u003e(())()\u003c/span\u003e。$$$s$$$ 的成本将等于 $$$3 + 1 + 1 \u003d 5$$$。\u003c/p\u003e\u003cp\u003e在第二个测试用例中,唯一的选择是将 $$$s$$$ 设为 \u003cspan class\u003d\"tex-font-style-tt\"\u003e()\u003c/span\u003e,成本为 $$$1$$$。\u003c/p\u003e\u003cp\u003e在第三个测试用例中,唯一可能的 RBS 是 \u003cspan class\u003d\"tex-font-style-tt\"\u003e()()()()\u003c/span\u003e,成本为 $$$1 + 1 + 1 + 1 \u003d 4$$$。\u003c/p\u003e\u003cp\u003e在第四个测试用例中,最优选择是将 $$$s$$$ 设为 \u003cspan class\u003d\"tex-font-style-tt\"\u003e(())(())\u003c/span\u003e,成本为 $$$3 + 1 + 3 + 1 \u003d 8$$$。\u003c/p\u003e"}}]}