31847번 - 문자열 접기 (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 $