题目描述

远疆之地常年被冰雪覆盖，时而刮过的风裹挟着细雪，皓白的雪原万分茫然，而在极北之地坐落着遗失的斯莫菲尔宫，旅行者 @zls_XICK 长途跋涉至此，推开宫殿大门，雪色与火把映衬下，是一串刻在青石上的符文。

宫殿内有诸多青石横向排列，每个青石上都刻有一个符文，这些符文共同组成了一串由小写字母组成的字符串 $S$，为了解开斯莫菲尔宫的秘密，他查看了前辈留下的皮质笔记，上面记载道，只需要将青石按照上面的字母从小到大或从大到小排列即可。

但是，旅行者 @zls_XICK 的力气有限，搬不动这些青石，但他发现这些青石似乎蕴含着几分神力，他把双手放在相邻的两块青石上，除了这两块青石外其余的青石悬凝飞起，进行了一定的排序，经过多次尝试，他发现青石排序的规则是固定的：

• 将手放在第 $i$ 和 $i+1$ 个青石上，这两个青石左侧的 $i-1$ 个青石会倒序排列后飞至第 $i+1$ 个青石右端，同时，原本这两个青石右侧的青石也会倒序排列后飞到第 $i$ 个青石左端。

现在兮雪纷纷，为了尽早完成探索，@zls_XICK 想知道双手最少需要放置几次才能使青石上的字母从大到小或从小到大排列。

输入格式

输入包括一行一个字符串 $S$，表示原来青石上字母符文排列。

输出格式

输出一行一个整数，表示最少操作次数。

dbca

1

数据规模与约定

设字符串 $S$ 长度为 $L$。

对于 $40\%$ 的数据满足 $1 \le L \le 10^3$。

对于 $100\%$ 的数据满足 $1 \le L \le 10^6$。