Dale 'n' Chip

Dale과 Chip은 매년 열리는 Fantastic Party for Chipmunks(FPC)를 준비하고 있다. 이들의 말에 따르면 올해 파티는 견과류를 잔뜩 차리는 잔치 그 이상이다. 사실 이들은 친구들을 위해 게임도 준비했다. 다른 다람쥐들과 마찬가지로 이들도 게임 결과가 예측 가능하기를 원한다. 놀라운 일은 용납할 수 없다. 가장 피하고 싶은 것은 화가 난 채 진 다람쥐가 나오는 것이다. 그래서 모두가 정확히 한 번씩 이기고 한 번씩 지도록 게임을 비밀리에 설계한다.

게임은 이렇게 진행된다. 다람쥐들이 원형으로 둘러앉는다. 그중 한 명이 오른쪽 이웃에게 몸을 돌려 가위바위보를 한 번 한다. 그다음에는 방금 상대였던 오른쪽 이웃이 자기 오른쪽 이웃과 가위바위보를 하고, 이것이 계속 이어진다. 모든 다람쥐가 오른쪽 이웃과 정확히 한 번씩 가위바위보를 마치면 게임이 끝난다.

Dale에게는 파티에 참석할 다람쥐 명단이 있다. Chip은 각 다람쥐가 항상 낼 손 모양(바위, 보, 가위)을 알고 있다. 일부 다람쥐는 예측 가능하기 때문이다. 모든 다람쥐가 같은 시간에 오는 것은 아니므로, 이들은 참석자 명단의 여러 부분 목록에 대해 게임을 준비하려 한다. 각 부분 목록에 대해, 누가 먼저 시작하든 모든 다람쥐가 행복하도록 원형으로 배치할 수 있는 다람쥐의 최대 수를 구하라.

행복한 다람쥐는 정확히 한 번 이기고 정확히 한 번 진 다람쥐를 뜻한다.

입력은 다음과 같다.

• 첫 줄에 정수 $n$ ($1\leq n\leq 10^4$)이 주어진다. 참석 예정자 명단에 있는 다람쥐의 총수이다.
• 다음 $n$개의 줄에는 각 참석자가 항상 낼 손 모양이 한 줄에 하나씩 주어진다. 손 모양은 "Rock", "Paper", "Scissors" 중 하나이다.
• 다음 줄에 정수 $q$ ($1\leq q\leq 10^5$)가 주어진다. Dale과 Chip이 게임을 준비하려는 부분 목록의 개수이다.
• 다음 $q$개의 줄에는 각각 두 정수 $s$와 $e$ ($1 \leq s \leq e\leq n$)가 주어진다. 모든 $s \leq i \leq e$를 만족하는 다람쥐 $i$로 이루어진 부분 목록을 뜻한다.

$q$개의 부분 목록마다 한 줄에 답을 출력한다. 답은 해당 부분 목록에서 골라 원형으로 배치했을 때 모든 다람쥐가 행복해지는 다람쥐 수의 최댓값이다.