Minuses

Subtraction is not associative. For example $(5-2)-1=2$ but $5-(2-1)=4$, so $(5-2)-1 \ne 5-(2-1)$. This means the value of an expression such as $5-2-1$ depends on the order in which the subtractions are performed. When there are no brackets we agree to evaluate from left to right, so $5-2-1$ means $(5-2)-1$.

You are given an expression of the form $x_1 \pm x_2 \pm \dots \pm x_n,$ where each $\pm$ is either $+$ or $-$, and $x_1, x_2, \dots, x_n$ are pairwise distinct variables.

We want to insert brackets into the all-minus expression $x_1 - x_2 - \dots - x_n$ so that it becomes equivalent to the given expression (the two expressions are equal for every value of the variables). At most $n-1$ pairs of brackets may be inserted, and no pair of brackets may enclose zero or one variable.

For example, to match $x_1 - x_2 - x_3 + x_4 + x_5 - x_6 + x_7$ we may bracket $x_1 - x_2 - x_3 - x_4 - x_5 - x_6 - x_7$ as $((x_1-x_2)-(x_3-x_4-x_5))-(x_6-x_7).$ This is only one of many possible bracketings, and it is not necessarily one that uses the fewest pairs. Determine the minimum number of bracket pairs over all valid bracketings.

The first line contains an integer $n$ ($2 \le n \le 10^6$), the number of variables in the given expression. Each of the next $n-1$ lines contains a single character, $+$ or $-$. The $k$-th of these lines ($1 \le k \le n-1$) is the sign between $x_k$ and $x_{k+1}$ in the given expression. You may assume that a valid bracketing always exists for the input.

Print a single integer: the minimum number of bracket pairs that must be inserted into $x_1 - x_2 - \dots - x_n$ to obtain an expression equivalent to the given one.