31805번 - 문자열 수정 스페셜 저지

문제

이안이는 문자열 연구를 하고 있다. 문자열로 팰린드롬도 없애보고 복사도 해보고 많은 실험을 해봤다. 하지만 문자열 하나만으로는 실험을 하기에 부족하다고 생각했다. 이안이는 아직 학생이라 새로운 문자열을 사기에는 돈이 없다. 그래서 쓰던 문자열을 바꾸어 쓰기로 했다.

실험실에는 문자열 마법사 고은이와 가은이가 있다. 이안이는 고은이와 가은이를 찾아가 완전 새로운 문자열을 만들어달라고 부탁했다. 완전 새로운 문자열은 기존 문자열과 구성이 같지만, 모든 글자가 이전과 같은 위치에 있지 않은 문자열이다. 단, 글자의 종류가 같으면 동일하게 취급한다.

고은이와 가은이는 원하는 글자 위에 서서 서로의 위치에 있는 글자를 교환하는 방법으로 문자열을 바꿔준다. 글자가 굉장히 무겁기 때문에 고은이와 가은이는 글자를 최대한 적게 바꾸고 싶어한다. 고은이와 가은이를 도와 이안이의 문자열을 완전 새로운 문자열로 바꾸기 위해 필요한 최소 횟수를 구해주자.

입력

첫 번째 줄에 이안이의 문자열의 길이 $N$이 주어진다.

두 번째 줄에 이안이의 문자열이 주어진다. 문자열은 영문 소문자로만 이루어져 있다.

출력

첫 번째 줄에 문자열을 고치는 데 필요한 최소 횟수를 한 줄에 출력한다. 만약 어떤 방법으로도 완전 새로운 문자열을 만들 수 없다면 -1을 출력한다.

만약 완전 새로운 문자열을 만들 수 있다면, 두 번째 줄부터 글자를 교환할 때마다 고은이와 가은이의 위치를 공백으로 구분하여 출력한다. 이때, 더 왼쪽에 있는 사람의 위치부터 출력해야 한다. 위치는 왼쪽 첫 번째 글자부터 몇 번째 글자에 있는지를 나타내는 양의 정수이다.

제한

• 1ドル \le N \le 200,000円$

노트