幼儿园老师终于设法让所有的孩子排成一队，准备步行前往公交车站参加每周一次的郊游。他们之前没考虑到的是，今天不同的孩子要去不同的地方郊游。他们应该排成一队前往公交车站，但为了避免到达车站时出现混乱，所有去动物园的孩子应该排在队伍的最前面，去湖边的孩子排在中间，而剩下的去科学博物馆的孩子应该排在最后。

由于让所有孩子排好队需要花费大量时间，因此不允许任何孩子离开队伍。为了按郊游目的地整理队伍，相邻的孩子可以交换位置。现在幼儿园老师想知道，他们是否有足够的时间完成这项工作并赶上公交车。

任务

给定一个由数字 0、1 和 2 组成的序列，表示队伍中从前到后每个孩子的郊游目的地。相邻的孩子可以交换位置，队伍最终应按目的地数字从小到大排列，即以 0 开头，以 2 结尾。请问将队伍整理好所需的最少交换次数是多少？

输入格式

输入仅包含一行，为一个由字符 0、1 或 2 组成的字符串，表示孩子们的目的地。字符串的长度不超过 1 000 000 个字符。

输出格式

输出一行，包含一个整数，表示将孩子们按顺序排列所需的最少交换次数。

样例

样例输入 1

10210

样例输出 1

5