Paper Clips

Little Bytedragon found a new game: hooking paper clips into a chain. One day he emptied his father's box of clips, built one very long chain, and went off to school. His father needs all of those clips back, and he needs them separated.

Before he starts pulling the chain apart, he wants to know how long it will take.

The father has one kind of move: he picks a single clip and turns it by 180 degrees around an axis perpendicular to the table top. A move takes exactly one second. The pictures below show a few such moves on a short chain.

↓

↓

↓

Fig. 1: the first few moves of taking a chain apart.

Write a program that

• reads the description of the chain from standard input,
• computes the smallest number of moves needed to take the chain apart into single clips,
• writes that number to standard output.

The chain is described by the position of every clip in it and by the way each neighbouring pair is joined.

Seen from above, a clip lying on the table is in one of four positions.

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

Fig. 2: the four positions of a clip on the table.

Two neighbouring clips are joined in one of two ways. The top part of the left clip runs above the top part of the right clip, or it runs below it. Both cases are drawn here.

(P)	(Q)

Fig. 3: the two joints, drawn for the pair BA.

The first line contains one integer $n$ ($2 \le n \le 5\,000\,000$), the number of paper clips.

The second line contains the chain as a string of exactly $2n-1$ characters. The characters in positions $1, 3, 5, \dots, 2n-1$ are the positions of the clips from left to right, each of them A, B, C or D. The characters in positions $2, 4, \dots, 2n-2$ are the joints between neighbouring clips, each of them P or Q.

Print one integer, the smallest number of moves that separates the chain into single paper clips.

The chain in the sample input is the one drawn in figure 1. Four moves are enough when the father departs from the order shown in that picture.