에코에코

번역기의 오작동 때문에 이름을 얻은 외계인 에코 에코 이야기를 알고 있을 것이다. 그 작은 외계인은 성탄절 뒤 정리를 돕기 위해 다시 지구에 돌아왔다. 그런데 에코 에코의 번역기가 또 고장 났다.

이번에는 번역기가 단어를 반복할 뿐만 아니라 단어 안 글자의 순서도 바꾼다. 예를 들어 단어 “slon”은 먼저 “slonslon”이 되고, 그다음 글자 순서가 바뀌어 “slosnoln”이나 “soolnlsn” 등이 될 수 있다. 에코 에코의 번역기가 잘못 번역한 단어를 단순한 반복으로 이루어진 단어로 만들기 위해 필요한 인접한 글자 교환 횟수에 따라 번역기를 고치는 데 필요한 금화의 양이 달라진다.

예를 들어 에코 에코의 번역기가 어떤 단어를 “soolnlsn”으로 번역했다면, 인접한 글자를 네 번 교환해서 반복으로 이루어진 단어 “olsnolsn”을 얻을 수 있으므로(세 번째 예제의 설명 참고) 금화 네 닢이면 번역기를 고칠 수 있다. 이런 교환을 거쳐 얻은 단어가 에코 에코가 원래 말하려던 단어일 필요는 없다. 이는 번역기를 고치는 데 필요한 금화의 양에 영향을 주지 않는다.

에코 에코를 돕고 싶지만 어머니의 장신구를 많이 훔치면 크리스마스 선물을 받지 못한다. 그래서 에코 에코의 번역기에서 나온 단어가 주어졌을 때, 단순한 반복으로 이루어진 단어를 얻기 위해 필요한 인접한 글자 교환 횟수의 최솟값을 구하려고 한다.

첫째 줄에는 양의 정수 $n$이 주어진다. 이는 에코 에코가 말하려는 단어의 길이이다.

둘째 줄에는 $2n$개의 문자가 주어지며, 각 문자는 라틴 알파벳 소문자이다. 이는 에코 에코의 번역기에서 나온 단어를 나타낸다. 각 문자는 짝수 번 나타난다.

에코 에코의 단어를 단순한 반복으로 이루어진 단어로 만들기 위해 필요한 인접한 글자 교환 횟수의 최솟값을 한 줄에 출력한다.

모든 부분 문제에서 $1 ≤ n ≤ 100\,000$이다.

세 번째 예제의 설명: soolnlsn에서 네 번의 교환으로 단순한 반복 단어를 얻는 한 가지 방법은 다음과 같다.

soolnlsn → solonlsn → solnolsn → oslnolsn → olsnolsn