문자열 접기 (Hard)

기다란 종이에 알파벳 대문자로만 이루어진 문자열이 한 줄로 쓰여 있다. 예를 들어 아래 그림과 같이 종이에 “ABAACA”가 쓰여 있다고 가정하자.

이제 이 종이를 한 번만 접을 것이다. 종이는 서로 이웃한 문자 사이에서만 접을 수 있다. 예를 들어 아래 그림과 같이 위 종이를 $4$번째 문자와 $5$번째 문자 사이에서 접을 수 있다.

이때 서로 맞닿은 문자 쌍 중에서, 서로 같은 문자가 맞닿은 쌍의 개수가 이 접기의 점수가 된다. 예를 들어 앞에서의 접기의 점수는 $1$점이 된다. 하지만 아래 그림과 같이 $3$번째 문자와 $4$번째 문자 사이에서 종이를 접으면 점수는 $2$점이 된다.

이제 여러분은 알파벳 대문자로만 이루어진 문자열 $S$가 주어질 때, 다음과 같은 질문 $Q$개에 답해야 한다.

• $l \ r$: 문자열 $S$의 $l$번째 문자, $\left( l+1 \right)$번째 문자, $\cdots$, $r$번째 문자가 차례대로 종이에 쓰여 있을 때, 종이를 한 번 접어서 얻을 수 있는 최대의 점수는 몇 점인가?

첫 번째 줄에 문자열의 길이를 나타내는 정수 $N$이 주어진다.

두 번째 줄에 알파벳 대문자로만 이루어진 문자열 $S$가 주어진다.

세 번째 줄에 정수 $Q$가 주어진다.

네 번째 줄부터 $Q$개 줄에 걸쳐 위에서 설명한 질문을 나타내는 정수 $l$, $r$이 공백으로 구분되어 주어진다.

각 질문의 답을 나타내는 정수를 순서대로 한 줄에 하나씩 출력한다.

• $2 \le N \le 5{,}000$
• $1 \le Q \le 200{,}000$
• $1 \le l \lt r \le N$