Palindrome Check 2

Ian has a string $S$ of length $N$, where each character is one of the lowercase English letters (a, b, $\cdots$, z). If reading the characters of $S$ from back to front gives exactly $S$, then $S$ is a palindrome. For example, abccba is a palindrome, but abccbba is not. Eunseong knows some of the characters of $S$ and wants to decide whether $S$ is a palindrome. Knowing only some characters may not be enough, so Eunseong can ask Ian the following kind of query.

• Eunseong asks Ian for a pair $(i, c)$, where $i$ is an integer with $1 \le i \le N$ and $c$ is a lowercase letter.
• Ian answers 1 if the $i$-th character of $S$ from the left is $c$, and 0 otherwise.

Eunseong does not want to bother Ian, so Eunseong wants to decide whether $S$ is a palindrome with as few queries as possible. Ian answers each query right away, so the next query can depend on earlier answers. Find the smallest $K$ such that Eunseong can decide whether $S$ is a palindrome with at most $K$ queries, no matter what $S$ is.

The first line contains the integer $N$.

The second line contains a string $T$ of length $N$. For each $1 \le i \le N$, if the $i$-th character of $T$ is a lowercase letter, Eunseong knows that the $i$-th character of $S$ equals the $i$-th character of $T$. If the $i$-th character of $T$ is ?, Eunseong does not know the $i$-th character of $S$.

Print on the first line the minimum number of queries that guarantees Eunseong can decide whether $S$ is a palindrome.

• $1 \le N \le 200\ 000$
• Each character of $S$ is a lowercase English letter or ?.