括号序列
题号：NC18416
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

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

输出描述:

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

输入

复制 
6
(()))(

输出

复制 
1
示例2

输入

复制 
6
)))(((

输出

复制 
2

备注:

对于80%的数据：n≤3000
对于100%的数据，n≤5×106