32516번 - 팰린드롬 판별하기 2

이안이는 길이가 $N$이고 각 문자는 영문 알파벳 소문자(a, b, $\cdots$, z) 중 하나인 문자열 $S$를 가지고 있다. $S$의 문자들을 뒤에서 앞으로 배열한 문자열이 $S$와 정확하게 일치하면 $S$를 팰린드롬이라고 한다. 예를 들어서 abccba는 팰린드롬이지만 abccbba는 팰린드롬이 아니다. 은성이는 $S$의 일부 문자들을 알고 있고, $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$의 각 문자는 영문 알파벳 소문자 또는 ?이다.