Jungol

중복문자열이란, 길이가 짝수이며 앞쪽 절반의 부분문자열이 뒤쪽 절반의 부분문자열과 같은 문자열을 일컫는다.

예를 들어, abcabc는 중복문자열이지만 ababab는 중복문자열이 아니다.

길이 2N의 문자열에서 인접한 위치의 문자를 교환하는 연산을 적절히 시행하여 전체 문자열이 중복문자열이 되도록 하고 싶다.

인접한 위치의 문자를 교환하는 연산의 최소 시행 횟수를 구하시오.

입력

첫 줄에 N이 주어진다. (1<=N<=100000)

그 다음 줄에 길이 2N의 영어 소문자로 구성된 문자열이 주어진다.

단, 이 문자열은 항상 중복문자열이 되도록 할 수 있다.

출력

중복문자열이 되게 하는 연산의 최소 횟수를 한 줄에 출력하시오.

부분문제

번호	점수	조건
#1	10점	문자열에 'a'가 N개, 'b'가 N개 주어진다.
#2	20점	각 문자는 최대 2번 등장한다.
#3	20점	앞쪽 절반의 문자의 집합과 뒤쪽 절반의 문자의 집합이 같다. (중복 고려)
#4	20점	N<=1000
#5	30점	제한 없음

예제1

예제2

예제3

soolnlsn -> solonlsn -> solnolsn -> oslnolsn -> olsnolsn

출처

COCI 2021/2022 Contest #3

중복문자열 1초 1024MB