题目内容

灯带车间今晚要按工艺单给一条展台灯带上色。值班员可以一次喷出若干格相同色号，也可以把喷头挪到任意空隙再喷，但色号的启用顺序必须按字典序不降，否则调色阀会锁死。请算出最少要启动多少次喷涂。

灯带最终必须变成串 $w$，且 $w$ 只由小写字母构成，每个字母表示一种色号。值班员可以做两类动作：

• 喷涂：选定某个色号 $x \in \{a,\dots,z\}$ 和一个正整数 $k$，在当前喷头位置一次喷出连续 $k$ 格色号 $x$，记为 $1$ 次喷涂。
• 挪喷头：把喷头移到当前灯带的任意空隙（含两端），挪动次数不计入答案。

所有喷涂必须满足字典序不降：若某次喷了色号 $x_1$，下一次喷的色号 $x_2$ 必须满足 $x_2 \ge x_1$。也就是说，一旦喷过例如 c，就不能再喷 a 或 b。

给定目标串 $w$，请计算在上述约束下得到 $w$ 所需的最少喷涂次数。

目标串长度满足 $1 \le |w| \le$ 100000，且 $w$ 只含小写字母。

输入描述

输入一行仅由小写字母构成的字符串 $w$（$1 \le |w| \le$ 100000），表示目标灯带。

输出描述

输出一个整数，即得到目标灯带所需的最少喷涂次数。

样例1

输入

bab

输出

3

说明

色号必须不降，不能先喷完 b 再喷 a。一种做法：先喷 1 格 a，再在左侧喷 1 格 b，最后在右侧再喷 1 格 b，共 3 次。两个 b 被已经就位的 a 隔开，不能一次喷完。

样例2

输入

aabbaa

输出

2

说明

先一次喷出 4 格 a，再把喷头挪到中间一次喷出 2 格 b，得到 aabbaa。更大的色号后喷，可以把已经连在一起的较小色号从中间拆开，所以不必按成品上的三段分别喷涂。

样例3

输入

dcba

输出

4

说明

色号严格递减，后喷的较小色号会被禁止，因此每个字母各喷一次，再靠挪喷头排成目标顺序。