팰린드롬 판별하기 2

시간 제한1초메모리 제한1024 MB

요약

일부 문자가 정해지지 않은 문자열에서 위치 i의 문자가 c인지 묻는 질의로 팰린드롬 여부를 확정하는 데 필요한 최소 질의 수를 구합니다.

난이도: 보통10점 중 5점
유형: 문자열, 수학, 게임 이론
정답자: 아직 제출이 없습니다

문제

이안이는 길이가 $N$ 이고 각 문자가 영문 알파벳 소문자(a, b, $\cdots$ , z) 중 하나인 문자열 $S$ 를 가지고 있다. $S$ 의 문자들을 뒤에서 앞으로 배열한 문자열이 $S$ 와 정확히 일치하면 $S$ 를 팰린드롬이라고 한다. 예를 들어 abccba는 팰린드롬이지만 abccbba는 팰린드롬이 아니다. 은성이는 $S$ 의 일부 문자를 알고 있고, $S$ 가 팰린드롬인지 판별하려고 한다. 하지만 일부 문자만으로는 판별하기에 충분하지 않을 수 있으므로, 은성이는 이안이에게 다음과 같은 질의를 할 수 있다.

은성이는 이안이에게 정수 $i (1 \le i \le N)$ 와 알파벳 소문자 $c$ 의 순서쌍 $(i, c)$ 를 질의한다.
이안이는 $S$ 의 왼쪽에서 $i$ 번째 문자가 $c$ 이면 $1$ , 아니면 $0$ 으로 답한다.

은성이는 이안이를 귀찮게 하고 싶지 않아서, 가능한 한 적은 질의로 팰린드롬 여부를 판별하려고 한다. 이안이는 질의에 즉시 답하므로, 다음 질의는 앞선 답변에 따라 달라져도 된다. 은성이가 이안이에게 $K$ 번 이하로 질의하면 $S$ 가 어떤 문자열이든 팰린드롬 여부를 판별할 수 있음이 보장되는 최소의 $K$ 를 구하여라.

입력

첫째 줄에 정수 $N$ 이 주어진다.

둘째 줄에 길이가 $N$ 인 문자열 $T$ 가 주어진다. 각 $1 \le i \le N$ 에 대하여, $T$ 의 $i$ 번째 문자가 알파벳 소문자이면 은성이는 $S$ 의 $i$ 번째 문자가 $T$ 의 $i$ 번째 문자와 같다는 것을 알고 있다. $T$ 의 $i$ 번째 문자가 ?이면 은성이는 $S$ 의 $i$ 번째 문자를 알지 못한다.

출력

첫째 줄에 은성이가 팰린드롬 여부를 판별할 수 있도록 보장하는 최소의 질의 횟수를 출력한다.

제한

$1 \le N \le 200\ 000$
$S$ 의 각 문자는 영문 알파벳 소문자 또는 ?이다.

예제3

예제 1
입력
```
5
a???b
```
예상 출력
```
0
```
예제 2
입력
```
6
abccb?
```
예상 출력
```
1
```
예제 3
입력
```
9
abc?????a
```
예상 출력
```
28
```