줄넘기

면접 대비

시간 제한2초메모리 제한256 MB

요약

각 질의 구간 [l, r] 안에서 양 끝 높이가 같고 사이에 같은 높이가 없는 가장 긴 구간의 학생 수를 구합니다. 해당하는 구간이 없으면 0을 출력합니다.

문제

$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$ 개의 줄에는 각각 두 정수 $l_i$ , $r_i$ 가 주어집니다.

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