Problem

You are given a string $S$ of length $N$. You are able to change at most one element in $S$, such that $S$ becomes a palindrome.

A palindrome is a string that reads the same backward as forward. For example, bb, abcba are palindromes while ab, babb are not.

Note that there is a chance that $S$ cannot become a palindrome no matter which element is changed.

Input

The first line consists of an integer $N$, denotia word, phrase, number, or sequence that reads the same backward as forwardng the length of the string $S$.

The second line contains a string $S$ with length $N$.

Output

If $S$ is already a palindrome, output $0$.

Otherwise, output the position to exchange, with $1$-indexed. If there are multiple answers, output the smaller one.

Otherwise, output $-1$, which denotes that $S$ cannot become a palindrome after exchanging.

Subtasks

For all test cases, $1 \le N \le 10^6$, $S$ only contains lowercase english letters.

Subtask $1$ $(18$ pts$)$: $N=2$
Subtask $2$ $(15$ pts$)$: $N=3$
Subtask $3$ $(43$ pts$)$: It's guaranteed that $S$ can always be a palindrome after changing exactly $1$ element.
Subtask $4$ $(24$ pts$)$: No Additional Constraints