题目描述

括號有許多種類，如：大括號 {}、中括號 []、以及小括號 ()。

在本題中，我們僅考慮小括號。括號通常成對使用，如果一個由括號組成的序列具有巢狀結構 (nested structure)，我們稱此序列為「格式正確」。

例如：

• 序列 $A=a_1a_2\cdots a_{6}=$()(()) 是格式正確的；
• 序列 $B=b_1b_2\cdots b_{5}=$(()() 則不是格式正確的，因為沒辦法在滿足每個右括號只能被配對一次的條件下，讓每個左括號都能配對到它後面的其中一個右括號。

更正式的說，「格式正確」可以定義如下：

一個由括號構成的序列 $P=p_1p_2p_3\cdots p_n$ 為格式正確，若同時滿足以下兩個條件：

1. 由左到右掃描 $p_1$ 到 $p_n$，在過程中任一位置的右括號 ) 的數量都不超過左括號 ( 的數量。
2. 序列中左括號的總數等於右括號的總數。

PorgramText 是一家軟體公司，正在為程式設計師開發一款全新的文字編輯器。這款編輯器將提供許多強大的功能，其中之一是自動修正輸入錯誤。

在觀察使用者的輸入行為後，PorgramText 發現許多程式設計師因打字速度太快，常常不小心多輸入左括號或右括號。為了解決這個問題，編輯器將提供一項功能：將一個可能「格式不正確」的括號序列 $P$ 自動轉換為「格式正確」的序列 $P^\prime$。在轉換過程中，唯一允許的操作是刪除左括號或右括號。

PorgramText 想要讓你幫助他們：計算最少需要刪除多少個括號，才能讓 $P$ 轉換成一個「格式正確」的序列。

输入格式

$$\begin{aligned} & n \\ & P_1P_2\cdots P_n \\ \end{aligned}$$

• $n$ 代表括號序列的長度。
• $P$ 是由 ( 和 ) 組成的括號序列。

输出格式

$$ans$$

• $ans$ 代表最少需要刪除的括號數量。

6
()(())

0

5
(()()

1

3
)((

3

提示

測資限制

• $1 \leq n \leq 10^5$。
• $P$ 僅包含 ( 與 )。

評分說明

本題共有三組子任務，條件限制如下所示： 每一組可能包含一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

子任務	分數	額外輸入限制
1	30	所有左括號的出現位置均早於所有右括號（因此左右括號不會交錯出現）。
2		$ans$ 只可能會是 $0$ 或 $2$。（註：只需判斷 $P$ 是否為「格式正確」。）
3	40	無額外限制。