合唱编排

题目描述

森林小鸟合唱团正在排练一首特殊的合唱曲目。在这首曲目中，每只小鸟的单次完整演唱必须严格遵循固定的旋律 chirp：即 按顺序依次发出音符 c$\to$h$\to$i$\to$r$\to$p，中途不能跳音或中断。当一只小鸟完成一段完整的 chirp 旋律后，可立即从头开始演唱新的 chirp，也可间隔任意时长再演唱。

合唱乐谱（字符串 $s$）以“音拍”为单位记录演唱过程：每个音拍对应且仅对应某一只小鸟当前正在唱的音符，字符串的顺序就是音拍的先后顺序。例如：

• 若小鸟A在第1音拍唱 c，小鸟B在第2音拍唱 c，小鸟A在第3$\sim$ 6音拍依唱 h,i,r,p，小鸟B在第7$\sim$ 10音拍依唱 h,i,r,p，则乐谱为“cchirphirp”
• 若小鸟A在第1$\sim$5音拍依唱 c,h,i,r,p，随后在第6音拍开始重新唱 c,h,i,r,p，则乐谱为“chirpchirp”

请你根据给定的乐谱计算出：完成所有音拍的演唱，至少 需要多少只小鸟。

特别地，不保证乐谱合法，如果乐谱不合法，则无解并返回 -1。例如违背 chirp 的顺序性、完整性等。

输入格式

第一行一个整数 $n$，代表乐谱字符串的长度

第二行一个字符串 $s$，代表乐谱

输出格式

一行一个整数代表答案

输入输出样例

输入 #1

10
cchirphirp

输出 #1

2

输入 #2

10
chirpchirp

输出 #2

1

输入 #3

8
chirpchi

输出 #3

-1

样例解释

对于样例 $1$，最少需要两只小鸟完成演唱（演唱加粗显示），第一只小鸟"cchirphirp"，第二只小鸟"cchirphirp"；

对于样例 $2$，一只小鸟演唱 chirp 两次；

对于样例 $3$，乐谱不遵循演唱规则，演唱 chirp 过程中不能中断。

数据范围

对于 $20\%$ 的数据，$1\le n \le 10^3,$ 保证字符串 $s$ 合法

对于 $40\%$ 的数据，$1\le n \le 10^5,$ 保证字符串 $s$ 合法

对于 $100\%$ 的数据，$1\le n \le 10^7,$ 不保证字符串 $s$ 合法