该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定括号长度N，给出一串括号（只包含小括号），计算出最少的交换（两两交换）次数，使整个括号序列匹配。
我们认为一个括号匹配，即对任意一个')'，在其左侧都有一个'('与它匹配，且他们形成一一映射关系。

Format

Input

第一行：整数N，表示括号序列长度
第二行：一个字符串，表示括号

Output

一个整数，表示最少的交换次数

Sample

Input1

6
(()))(

Output1

1

Input2

6
)))(((

Output2

2

Limitation

对于80%的数据：n≤3000
对于100%的数据，n≤5×10^6
1秒，256MB

Source

原创？