29770번 - 서로 다른 최대 구간 쿼리

문제

길이 $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)$

출력

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

제한

힌트