题目描述

英小文字からなる長さ $N$ の文字列 $S$ が与えられます．

あなたは，$S$ に対して以下の操作を好きな回数行えます．

• 先頭の文字と最後の文字が異なる連続した（非空な）部分列を選び，これを削除する．

$S$ を空文字列にすることが可能か判定し，可能な場合は必要な最小の操作回数を求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $S$

输出格式

$S$ を空文字列にすることが可能な場合，必要な最小の操作回数を出力せよ． 不可能な場合，$-1$ を出力せよ．

题目大意

给出一个由小写字母组成的长度为 $n$ 的字符串 $s$。

可以对 $s$ 进行以下操作：

• 删除一个首尾字符不相同的子串。

求最少多少次操作可使 $s$ 变成空串，如不能变成空串，输出 $-1$。

4
abba

2

3
aba

-1

提示

制約

• $2\ \leq\ N\ \leq\ 10^5$
• $S$ は英小文字からなる長さ $N$ の文字列

Sample Explanation 1

abba →（abを選んで削除）→ ba →（baを選んで削除）→ 空文字列 と操作すればよいです．