問題文

長さ $N$ の +,-,? からなる文字列 $S$ が与えられます。あなたは以下のルールに従って長さ $N$ の整数列 $A$ を作ります。

ここで、$S_i$ は文字列 $S$ の $i$ 文字目、 $A_i$ は整数列 $A$ の $i$ 番目の要素を表します。

• $S_i=$+ なら $A_i=1$ にする。
• $S_i=$- なら $A_i=-1$ にする。
• $S_i=$? なら $A_i=1$ または $A_i=-1$ にする。

作られた $A$ に対して、以下の問題の答えを $f(A)$ とします。

長さ $N$ の整数列 $A$ があり、 $A$ に対して以下の操作を行うことができます。

• 整数 $l,r \ (1 \leq l \leq r \leq N)$ を選び、 $A_l, A_{l+1}, \cdots , A_r$ それぞれの値を $-1$ 倍する。

以下の条件を達成するために必要な操作回数の最小値を求めてください。

• 条件：$B_i= \sum_{j=1}^{i} A_j$ とする。全ての $i$ について、 $B_i \geq 0$ が成り立つ。

$f(A)$ の 最小値 を求めてください。

入力

$N$
$S$

• $1 \leq N \leq 2 \times 10^5$
• $S$ は +,-,? からなる長さ $N$ の文字列
• $N$ は整数である。

出力

$f(A)$ の 最小値 を整数で出力してください。

サンプル

5
+--?-

1

4
??--

0

13
-?+++---?----

2