서로 다른 최대 구간 쿼리

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

요약

각 질의 [l,r]마다 그 안에서 원소가 모두 서로 다른 가장 긴 부분 구간의 길이를 구한다.

문제

길이 $N$ 의 수열 $A\_1, A\_2, ... A\_N$ 가 입력된다. 다음 쿼리를 수행하자.

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

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

첫째 줄에 $N$ 이 입력된다. $(1≤N≤500\\,000)$

둘째 줄에 정수 수열 $A\_1, A\_2, ... A\_N$ 이 공백으로 구분되어 입력된다. $(1≤A\_i≤N)$

셋째 줄에 $Q$ 가 입력된다. $(1≤Q≤500\\,000)$

넷째 줄부터 $Q+3$ 번째 줄까지 쿼리가 한 줄에 하나씩 입력된다. $(1≤l≤r≤N)$

쿼리가 주어질 때마다 쿼리의 답을 한 줄에 하나씩 출력한다.