题目描述

给定一个长度为 $N$ 的由小写英文字母组成的字符串 $S$。

你可以对 $S$ 执行以下操作任意次：

• 选择其非空的连续子串，使得第一个字符和最后一个字符不相同，并删除该子串。

判断是否能够使 $S$ 变为空字符串。如果可能，找到所需的最小操作次数。

约束条件

• $2 \leq N \leq 10^5$
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串。

输入

从标准输入读入数据，格式如下：

$N$ $S$

输出

如果可以使 $S$ 变为空字符串，则打印所需的最小操作次数。否则，打印 $-1$。

示例输入 1

4
abba

示例输出 1

2

我们应该按照以下方式操作：abba → （删除 ab） → ba → （删除 ba） → 空字符串。

示例输入 2

3
aba

示例输出 2

-1