Delete Delete

Problem Description

Given a string, you may delete several (possibly $0$) identical characters. After such operations, can you obtain a palindrome? If yes, find the minimum number of deletions.

Input Format

There are multiple test cases.

Each test case consists of two lines: the length $N$ of the string, and a string $S$ consisting only of lowercase letters.

Output Format

For each test case, output one line.

If it is impossible to get a palindrome, output $-1$. Otherwise output the minimum number of operations.

Sample Input

4
8
bilibili
3
qwq
9
daimayuan
7
xcpcxpc

Sample Output

1
0
-1
2

Sample Explanation

In the first example, deleting the leading b gives ilibili.

In the second example, qwq is already a palindrome, so no operation is needed.

In the third example, daimayuan cannot become a palindrome by deleting only one kind of character.

Constraints

• $1 \le N \le 10^5$, but $\sum N \le 2 \times 10^5$.