뺄셈과 괄호

뺄셈은 결합법칙이 성립하지 않는다. 예를 들어 $(5-2)-1=2$ 이지만 $5-(2-1)=4$ 이므로 $(5-2)-1 \ne 5-(2-1)$ 이다. 즉 $5-2-1$ 과 같은 식의 값은 뺄셈을 계산하는 순서에 따라 달라진다. 괄호가 없으면 왼쪽에서 오른쪽 순서로 계산하기로 약속하므로, $5-2-1$ 은 $(5-2)-1$ 을 뜻한다.

다음 형태의 식이 주어진다. $x_1 \pm x_2 \pm \dots \pm x_n$ 여기서 각 $\pm$ 는 $+$ 또는 $-$ 이며, $x_1, x_2, \dots, x_n$ 은 서로 다른 변수이다.

모든 부호가 뺄셈인 식 $x_1 - x_2 - \dots - x_n$ 에 괄호를 넣어, 주어진 식과 동치가 되도록(모든 변수 값에 대해 두 식의 값이 같아지도록) 만들려고 한다. 괄호는 최대 $n-1$ 쌍까지 넣을 수 있으며, 변수를 하나도 감싸지 않거나 하나만 감싸는 괄호는 넣을 수 없다.

예를 들어 $x_1 - x_2 - x_3 + x_4 + x_5 - x_6 + x_7$ 과 같아지게 하려면, $x_1 - x_2 - x_3 - x_4 - x_5 - x_6 - x_7$ 에 괄호를 넣어 $((x_1-x_2)-(x_3-x_4-x_5))-(x_6-x_7)$ 와 같이 만들 수 있다. 이는 가능한 여러 괄호 배치 중 하나일 뿐이며, 반드시 괄호 쌍의 개수가 최소인 배치는 아니다. 조건을 만족하는 모든 괄호 배치 중에서 사용한 괄호 쌍의 최소 개수를 구하여라.

첫째 줄에 정수 $n$ 이 주어진다 ($2 \le n \le 10^6$). 이는 주어진 식에 있는 변수의 개수이다. 다음 $n-1$ 개의 줄에는 각각 문자 $+$ 또는 $-$ 가 하나씩 주어진다. 그중 $k$ 번째 줄 ($1 \le k \le n-1$) 의 문자는 주어진 식에서 $x_k$ 와 $x_{k+1}$ 사이에 있는 부호이다. 입력으로 주어지는 식에 대해서는 조건을 만족하는 괄호 배치가 항상 존재한다고 가정해도 된다.

$x_1 - x_2 - \dots - x_n$ 에 괄호를 넣어 주어진 식과 동치가 되도록 만들 때 필요한 괄호 쌍의 최소 개수를 정수 하나로 출력한다.