← 返回题目列表

Codeforces · 1322/A

A. 不寻常的比赛

中文机器翻译题面 查看原题

如果通过插入“+”和“1”可以从中得到格式良好的数学表达式,则括号内的序列被称为正确(常规)。例如,序列“(())()”、“()”和“(()(()))”是正确的,而“)(”、“(()”和“(()))(”则不正确。

老师给德米特里的班级布置了一项非常奇怪的任务 - 她要求每个学生想出一个任意长度的序列,仅由左括号和右括号组成。之后,所有学生轮流命名他们发明的序列。轮到迪马的时候,他突然发现同学们都得到了正确的括号序列,而他是否得到了正确的括号序列,他不知道。

迪马现在怀疑他只是错过了任务陈述中的“正确”一词,所以现在他想通过稍微修改他的顺序来挽救局面。更准确地说,他可以任意次数(可能为零)执行重新排序操作。

重新排序操作包括选择序列的任意连续子段(子字符串),然后以任意方式重新排序其中的所有字符。这样的操作需要 $$$l$$$ 纳秒,其中 $$$l$$$ 是被重新排序的子段的长度。很容易看出,重新排序操作不会改变左括号和右括号的数量。例如,对于“))((”,他可以选择子字符串“)(”并重新排序“)()(”(此操作将花费$$$2$$$纳秒)。

由于迪马很快就要回答,他想尽快让他的顺序正确。帮助他做到这一点,或者确定这是不可能的。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — Dima 序列的长度。

第二行包含长度为 $$$n$$$ 的字符串,仅由字符“(”和“)”组成。

输出

打印一个整数 - 使序列正确所需的最小纳秒数,如果不可能,则打印“-1”。

示例

输入 #1

8
))((())(

输出 #1

6

输入 #2

3
(()

输出 #2

-1

注意

在第一个例子中,我们可以先将第一个字符到第四个字符重新排序,用“()()”替换,整个序列将是“()()())(”。然后将第七个到第八个字符重新排序,将其替换为“()”。最后序列将是“()()()()”,而总共花费的时间是$$$4 + 2 = 6$$$纳秒。