Preparing NOJ

One Occurrence

3000ms 786432K

Description:

You are given an array $a$ consisting of $n$ integers, and $q$ queries to it. $i$-th query is denoted by two integers $l_i$ and $r_i$. For each query, you have to find any integer that occurs exactly once in the subarray of $a$ from index $l_i$ to index $r_i$ (a subarray is a contiguous subsegment of an array). For example, if $a = [1, 1, 2, 3, 2, 4]$, then for query $(l_i = 2, r_i = 6)$ the subarray we are interested in is $[1, 2, 3, 2, 4]$, and possible answers are $1$, $3$ and $4$; for query $(l_i = 1, r_i = 2)$ the subarray we are interested in is $[1, 1]$, and there is no such element that occurs exactly once.

Can you answer all of the queries?

Input:

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5 \cdot 10^5$).

The third line contains one integer $q$ ($1 \le q \le 5 \cdot 10^5$).

Then $q$ lines follow, $i$-th line containing two integers $l_i$ and $r_i$ representing $i$-th query ($1 \le l_i \le r_i \le n$).

Output:

If there is no integer such that it occurs in the subarray from index $l_i$ to index $r_i$ exactly once, print $0$. Otherwise print any such integer.

Sample Input:

61 1 2 3 2 422 61 2

Sample Output:

40

Info

Provider CodeForces

Code CF1000F

Tags

data structuresdivide and conquer

Submitted 74

Passed 21

AC Rate 28.38%

Date 03/04/2019 16:28:50

Related

Nothing Yet