Background

真是太喜欢伊雷娜了！

Description

给定长度为$n$ $(1 \le n \le 10^6)$的只含有'(' 和 ')'的字符串，保证n为偶数。

你可以对该字符串进行数次操作，每一次操作你可以使该字符串中的两个字符交换。

现在提问：最少几次交换可以使括号完全匹配，括号完全匹配指每一个左括号必须要和一个右括号匹配，例如'()()()' 和 '(())()'是括号完全匹配，而'())(' 和 ')()('则不是

Format

Input

第一行给定一个数字$n$，代表字符串长度为$n$。

第二行给定长度为$n$的字符串。

Output

输出一行，包括一个数字，代表最少要交换的次数，如果无法使给定的字符串括号完全匹配，则输出'-1'。

Samples

4
(())

0

4
))()

-1

Limitation

1s, 1024KiB for each test case.