巨巨的提问
题号:NC16133
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

盼成巨巨是511的学神!
    有一天,宇鑫大佬在玩硬币,将硬币摆成一排,巨巨走过来看了一眼,向宇鑫大佬提出问题:“假如显示出正面的硬币为’(‘,反面的硬币为‘)’我可以将一段区间的括号同时翻转(‘(’<---->')'),至少需要多少次区间翻转将其变为合法的括号序列?”
面对巨巨的提问,宇鑫有点无助,请您帮帮他至少需要多少次。
合法括号序列是这样递归定义的:

1.()是合法括号序列;

2.如果A是合法的,那么(A)也是合法的;

3.如果A和B都合法,那么AB合法。


输入描述:

第1行:输入一个偶数n(2≤n≤2000)表示序列长度。

第2行:输入长度为n的括号字符串。

输出描述:

输出1行:需要翻转的最少次数。
示例1

输入

复制
6
()))))

输出

复制
1

说明

下标从1开始,翻转区间[3,4],就变成了()(()),翻转1次就合法了!