Description

给定一个长为 $N$ 的仅含小写英文字母的字符串 $S$ 你每次可以对字符串 $S$ 执行以下操作。

• 选定 $S_i,S_j$ 满足 $S_i \neq S_j$，删去 $i$ 到 $j$ 之间所有字符（包括 $S_i,S_j$）。

请问是否存在一种方案使得若干次操作后 $S$ 为空。若存在则输出最小的操作次数，否则输出 $-1$

Format

Input

第一行一个正整数 $N$ $(2 \leq N \leq 10 ^ 5)$，表示字符串的长度。 第二行一个仅含小写英文字母的字符串 $S$。

Output

如果能够成功操作使得字符串被删除成空串，输出一个整数表示最小操作数；否则输出 $-1$。

Samples

4
abba

2

说明

我们可以这样做：

删除 $\texttt{ab}$：$\texttt{abba} \to \texttt{ba}$；

删除 $\texttt{ba}$：$\texttt{ba} \to \texttt{空串}$。

3
aba

-1

Limitation

1s, 1024KiB for each test case.