24941번 - 줄넘기 서브태스크

$N$명의 학생들이 단체 줄넘기를 하기 위해 일렬로 서 있습니다. $i$번 학생의 키는 $A_i$입니다. 이 중 몇 명의 학생들을 뽑아 단체 줄넘기를 하려고 합니다. 이 과정은 아래와 같이 이루어집니다.

먼저, 단체 줄넘기 대표로 연속한 번호를 가진 학생들을 뽑습니다. $s$번 학생부터 $e$번 학생까지를 뽑았다고 해 봅시다. 이때, $s$번 학생과 $e$번 학생은 줄을 돌리고, 사이에 있는 나머지 학생들이 줄을 넘습니다.

줄을 잡는 두 학생의 키가 다르면 줄을 돌리기 어렵기 때문에, 줄을 잡는 두 학생의 키는 같아야 합니다. (즉, $A_s = A_e$) 또한, 그 사이에 키가 같은 학생이 또 있으면 방해되기 때문에, 나머지 학생들의 키는 모두 $A_s$와 달라야 합니다.

$Q$개의 질문이 주어집니다. $i$번째 질문에서 당신은 $l_i$ 이상 $r_i$ 이하의 번호를 가진 학생들만이 줄넘기에 참여할 수 있을 때, 줄넘기에 참여할 수 있는 학생 수의 최댓값을 반환해야 합니다. 만약 줄넘기가 이루어질 수 없다면, 0을 출력하세요.

첫 줄에는 학생의 수 $N$이 주어집니다.

둘째 줄에는 각 학생의 키 $A_1, A_2, \cdots, A_N$이 주어집니다.

셋째 줄에는 질문의 수 $Q$가 주어집니다.

넷째 줄부터 $Q+3$번 줄까지 $i+3$번 줄에는 두 정수 $l_i$, $r_i$가 주어집니다.

$Q$개의 질문에 대해, 줄넘기에 참여할 수 있는 학생 수의 최댓값을 한 줄에 하나씩 출력합니다. 만약 줄넘기를 할 수 없다면 0을 출력합니다.

• $2 \le N, Q \le 5 \times 10^5$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• $1 \le l_i < r_i \le N$ ($1 \le i \le Q$)