고르디우스의 춤

올해 열린 알고리즘 정복자 대회를 마무리하며, 대회 진행을 맡은 네 명의 심판(편의상 KC, KD, KO, KS라고 하자)이 즐거운 고르디우스의 춤을 추기로 했다. 고르디우스의 춤은 두 쌍의 무용수가 추는 바이트나라의 전통 춤이다.

무용수들은 정사각형 ABCD의 네 꼭짓점에 서서 두 쌍으로 나뉜다. 한 쌍은 A와 B, 다른 한 쌍은 C와 D이다. 각 쌍은 두 사람 사이에 끈을 팽팽하게 잡고 있으며, 처음에는 두 끈이 모두 수평으로, 서로 평행하게 놓여 있다.

춤은 여러 동작의 나열로 이루어지며, 각 동작은 다음 두 종류 중 하나이다.

• S: B와 C에 있는 두 무용수가 끈을 놓지 않은 채 자리를 바꾼다. 이때 B에 있던 무용수가 끈을 쥔 손을 위로 들어 올리고 C로 이동하면서, C에서 B로 오는 무용수를 자신의 팔 아래로 앞서 지나가게 한다.
• R: 모든 무용수가 끈을 놓지 않은 채 오른쪽으로 90도 회전한다. 즉 A에 있던 무용수는 B로, B에 있던 무용수는 C로, C에 있던 무용수는 D로, D에 있던 무용수는 A로 이동한다.

춤을 추는 동안 두 끈은 서로 엉키지만, 춤이 끝날 때에는 다시 풀려서 수평으로, 서로 평행하게 놓여야 한다. 이때 무용수들이 처음 자리로 돌아올 필요는 없다. 끈이 심하게 엉킬 수 있어서, 끈을 풀고 다시 수평이고 평행한 상태로 되돌리는 동작의 순서를 찾기가 쉽지 않다.

네 심판은 초보 무용수라서, 이미 시작한 춤을 끝내는 데 도움이 필요하다. 지금까지 수행한 동작의 순서가 주어질 때, 춤을 끝내기 위해(두 끈을 풀고 다시 수평이고 평행하게 만들기 위해) 추가로 필요한 동작의 최소 개수를 구하여라. 이 동작들을 마친 뒤 무용수들이 처음 위치에 있을 필요는 없다.

지금까지 수행한 동작의 순서를 입력받아 이 최소 개수를 출력하는 프로그램을 작성하여라.

첫째 줄에 지금까지 수행한 동작의 수를 나타내는 양의 정수 $n$이 주어진다 ($1 \le n \le 10^6$).

둘째 줄에는 길이가 $n$이고 문자 S와 R로 이루어진 단어가 주어진다. 이 단어의 각 문자는 순서대로 지금까지 수행한 동작을 나타낸다.

끈을 풀고 다시 수평으로 평행하게 만들기 위해 추가로 필요한 동작(각각 S 또는 R)의 최소 개수를 정수 하나로 출력한다.