cho.sh

뺄셈과 괄호

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

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

다음 형태의 식이 주어진다. x1±x2±⋯±xnx_1 \pm x_2 \pm \dots \pm x_n 여기서 각 ±\pm 는 ++ 또는 −- 이며, x1,x2,…,xnx_1, x_2, \dots, x_n 은 서로 다른 변수이다.

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

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

입력

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

출력

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