Informática Avançado - Semana 75

Uma ocorrência

Você recebe um vetor composto por $N$ números inteiros e $Q$ consultas sobre ele. A $i$ -ésima consulta é indicada por dois inteiros $l_i$ e $r_i$ . Para cada consulta, você deve encontrar qualquer número inteiro que ocorra exatamente uma vez no sub-array que vai do índice $l_i$ ao índice $r_i$ (um sub-vetor é um subsegmento contínuo de um vetor). Por exemplo, se a = [1,1,2,3,2,4], para a consulta ( $l_i$ = 2, $r_i$ = 6) o subvetor em que estamos interessados é [1,2,3,2,4] , e as respostas possíveis são 1, 3 e 4; para a consulta ( $l_i$ = 1, $r_i$ = 2), o subvetor em que estamos interessados é [1,1], e não existe um elemento que ocorre exatamente uma vez.

Você pode responder a todas as perguntas?

Entrada

A primeira linha contém um número inteiro $N$ ( $1\leq N \leq 5.10^5$ )
A segunda linha contém $N$ números inteiros $a_1$ , $a_2$ ,…, $a_n$ ( $1 \leq a_i \leq 5.10^5$ ).

A terceira linha contém um número inteiro $Q$ ( $1 \leq Q \leq 5.10^5$ )
Então $Q$ linhas seguem, a $i$ -ésima linha contendo dois inteiros $l_i$ e $r_i$ , representando a $i$ -ésima consulta ( $1 \leq l_i \leq r_i \leq n$ ).

Saída

Responda às consultas da seguinte maneira:
Se não houver um número inteiro tal que ocorra apenas uma vez no sub-vetor de índices $l_i$
e $r_i$ , imprima 0. Caso contrário, imprima qualquer número inteiro que satisfaça a condição.

Exemplos

ENTRADA	SAÍDA
6 1 1 2 3 2 4 2 2 6 1 2	4 0

Enviar solução: codeforces