종이 클립

바이트드래곤은 요즘 종이 클립을 서로 걸어 사슬 만드는 놀이에 빠져 있다. 어느 날 아버지의 클립을 몽땅 꺼내 아주 긴 사슬 하나를 만들어 놓고는 그대로 학교에 갔다. 하필 아버지에게 그 클립이 전부 필요하다. 그것도 하나씩 다 떨어진 상태로 필요하다.

아버지는 사슬을 풀기 전에 시간이 얼마나 걸릴지 알고 싶다.

사슬을 푸는 동작은 한 가지뿐이다. 클립 하나를 골라 책상 면에 수직인 축을 중심으로 180도 돌린다. 한 번 돌리는 데 정확히 1초가 걸린다. 아래 그림은 짧은 사슬에서 이 동작을 몇 번 이어서 한 모습이다.

↓

↓

↓

그림 1: 사슬을 푸는 과정의 처음 몇 동작.

다음을 수행하는 프로그램을 작성하시오.

• 표준 입력에서 사슬의 정보를 읽는다.
• 사슬을 낱개의 클립으로 분리하는 데 필요한 최소 동작 수를 구한다.
• 그 값을 표준 출력에 쓴다.

사슬은 왼쪽부터 놓인 클립의 방향과 이웃한 두 클립을 건 방식으로 나타낸다.

책상에 놓인 클립을 위에서 내려다보면 방향은 아래 네 가지 중 하나다.

(A)	(B)	(C)	(D)

그림 2: 클립이 책상에 놓이는 네 가지 방향.

이웃한 두 클립을 거는 방식은 두 가지다. 왼쪽 클립의 윗부분이 오른쪽 클립의 윗부분 위로 지나가거나, 반대로 아래로 지나간다. 두 경우를 아래에 그렸다.

(P)	(Q)

그림 3: BA 쌍으로 그린 두 가지 연결 방식.

첫째 줄에 클립의 개수 $n$이 주어진다 ($2 \le n \le 5\,000\,000$).

둘째 줄에 사슬을 나타내는 길이 $2n-1$짜리 문자열이 주어진다. $1, 3, 5, \dots, 2n-1$번째 문자는 왼쪽부터 센 각 클립의 방향이고 A, B, C, D 중 하나다. $2, 4, \dots, 2n-2$번째 문자는 이웃한 두 클립의 연결 방식이고 P 또는 Q다.

사슬을 낱개의 클립으로 분리하는 데 필요한 최소 동작 수를 한 줄에 출력한다.

예제 입력의 사슬이 그림 1에 그려진 사슬이다. 그림에 나온 순서를 따르지 않으면 네 번 만에 다 풀 수 있다.