Kindergarten Excursion

The kindergarten teachers finally got every kid into one line for the walk to the bus station. What they forgot is that today the kids are going to three different excursions. The group walks to the station as a single line, but to avoid chaos on arrival the kids going to the zoo have to stand at the front of the line, the ones going to the lake in the middle, and the ones going to the science museum at the back.

Getting the kids into a line took a long time, so no kid may step out of it. Two kids standing next to each other may swap places, and the line has to be reordered using only such swaps.

You are given a string of the characters 0, 1, and 2 giving the destination of each kid from the front of the line to the back. 0 is the zoo, 1 is the lake, and 2 is the science museum. Find the minimum number of swaps of adjacent characters needed to sort the string into the order 0, then 1, then 2.

The first line contains a string made up of the characters 0, 1, and 2. The length of the string is between 1 and 1,000,000.

Print one integer on the first line, the minimum number of swaps needed to order the line.