Kindergarten Excursion

Interview

Time limit1sMemory limit256 MB

Summary

Count the minimum adjacent swaps needed to reorder a string of 0s, 1s, and 2s into sorted order.

Level: Medium4 of 10
Topics: Sorting, Prefix sum
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples4

Example 1
Input
```
10210
```
Expected output
```
5
```
Example 2
Input
```
012
```
Expected output
```
0
```
Example 3
Input
```
210
```
Expected output
```
3
```
Example 4
Input
```
0
```
Expected output
```
0
```