서로 다른 최대 구간 쿼리

면접 대비

시간 제한1초메모리 제한1024 MB

요약

길이 N의 수열과 Q개의 구간 [l, r]이 주어질 때, 각 구간 안에서 모든 값이 서로 다른 가장 긴 연속 부분 구간의 길이를 구합니다.

문제

길이 $N$ 의 수열 $A_1, A_2, \ldots, A_N$ 이 주어진다. 다음 쿼리를 처리하자.

$l$ $r$ : $l \le s \le e \le r$ 을 만족하는 구간 $[s, e]$ 중에서 서로 다른 수만 있는 구간의 최대 크기를 출력한다. 구간 $[s, e]$ 의 크기는 $e-s+1$ 이다.

서로 다른 수만 있는 구간 $[s, e]$ 에는 $A_i = A_j$ 인 $i$ 와 $j$ 가 있어선 안 된다. ( $s \le i < j \le e$ )

첫째 줄에 $N$ 이 주어진다. ( $1 \le N \le 500\,000$ )

둘째 줄에 정수 수열 $A_1, A_2, \ldots, A_N$ 이 공백으로 구분되어 주어진다. ( $1 \le A_i \le N$ )

셋째 줄에 $Q$ 가 주어진다. ( $1 \le Q \le 500\,000$ )

넷째 줄부터 $Q+3$ 번째 줄까지 쿼리가 한 줄에 하나씩 주어진다. ( $1 \le l \le r \le N$ )

쿼리마다 답을 한 줄에 하나씩 출력한다.