섞인 메시지

Nikita는 오늘 메시지를 여러 개 받았다. 그중 하나는 암호 단어 "spbsu"였다. 이 암호 단어의 앞뒤에는 다른 메시지가 몇 개든 있었을 수 있다. 다른 메시지는 영어 소문자로 이루어진 임의의 문자열이다.

모든 메시지는 비밀 채널을 통해 하나씩 전송되었다. 따라서 채널의 문자열은 처음에 모든 메시지를 이어 붙인 것이었다.

하지만 채널은 잡음을 일으킬 수 있다. 서로 다른 메시지끼리 간섭할 수 있기 때문이다. 잡음은 자리 바꿈의 형태로 나타난다. 자리 바꿈 한 번에서 채널은 원래 서로 다른 메시지에 속했던 인접한 두 문자를 골라 맞바꾼다. 같은 메시지에 속한 문자끼리는 상대적인 순서가 유지된다.

모든 자리 바꿈이 끝난 뒤 Nikita는 결과 문자열을 받는다. 이 문자열이 주어졌을 때, 채널이 수행한 자리 바꿈 횟수의 최솟값을 구하라.

첫 줄에 받은 문자의 개수를 나타내는 정수 $n$이 주어진다. 이때 $5 \leq n \leq 10^5$이다.

다음 줄에는 Nikita가 받은 영어 소문자 $n$개로 이루어진 문자열 $s$가 주어진다. $s$는 위에서 설명한 과정의 결과임이 보장된다.

문제의 답인 정수 하나를 출력한다.