P15236 [NHSPC 2025] 括號問題

括號有許多種類，如：大括號 `{}`、中括號 `[]`、以及小括號 `()`。 在本題中，我們僅考慮小括號。括號通常成對使用，如果一個由括號組成的序列具有**巢狀結構 (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$ 代表最少需要刪除的括號數量。

### 測資限制 * $1 \leq n \leq 10^5$。 * $P$ 僅包含 `(` 與 `)`。 ### 評分說明 本題共有三組子任務，條件限制如下所示： 每一組可能包含一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。 | 子任務 | 分數 | 額外輸入限制 | | :----: | :--: | ------------- | | 1 | 30 | 所有左括號的出現位置均早於所有右括號（因此左右括號不會交錯出現）。 | | 2 | 30 | $ans$ 只可能會是 $0$ 或 $2$。（註：只需判斷 $P$ 是否為「格式正確」。） | | 3 | 40 | 無額外限制。 |