유치원 소풍

유치원 교사들이 아이들을 한 줄로 세워 버스 정류장까지 데려가려고 한다. 그런데 오늘은 아이들이 가는 소풍 장소가 서로 다르다. 정류장까지는 한 줄로 이동하되, 도착했을 때 혼란이 생기지 않도록 동물원에 가는 아이가 줄의 앞쪽에, 호수에 가는 아이가 가운데에, 과학관에 가는 아이가 뒤쪽에 서 있어야 한다.

줄을 다시 세우는 데는 시간이 오래 걸리므로 어떤 아이도 줄 밖으로 나올 수 없다. 대신 줄에서 바로 이웃한 두 아이는 자리를 서로 바꿀 수 있고, 이 교환만으로 줄을 정리해야 한다.

맨 앞 아이부터 맨 뒤 아이까지 각 아이의 소풍 장소를 0, 1, 2로 나타낸 문자열이 주어진다. 0은 동물원, 1은 호수, 2는 과학관이다. 이웃한 두 아이의 자리를 바꾸는 연산만 써서 문자열을 0, 1, 2 순서로 정렬하려고 할 때 필요한 교환 횟수의 최솟값을 구하여라.

첫째 줄에 문자 0, 1, 2로만 이루어진 문자열이 주어진다. 문자열의 길이는 1 이상 1,000,000 이하이다.

첫째 줄에 줄을 정리하는 데 필요한 최소 교환 횟수를 정수 하나로 출력한다.