题目描述

对于一个仅由左括号'('和右括号')'组成的字符串，鸭哥想知道它的最长合法前缀的长度是多少。对于某一个前缀，我们定义它是合法的，当且仅当该前缀满足以下条件：

存在一种拆分方案，可以将该前缀拆分为若干对匹配的括号'()',如:'()'，'()()'，'(())'都是合法的，而')()('，'))'是非法的。特殊的，空串我们认为也是合法的。

输入描述

第一行输入一个整数$n(1\le n\le 10^5)$，表示字符用的长度。

接下来一行输入一个长度为$n$的，仅由'('和')'组成的字符串。

输出描述

输出一个整数，表示最长的合法前缀长度。

样例

输入

5
(()))

输出

4

样例解释

可以证明前缀(())是最长且合法的前缀。