One Occurrence

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem

For each subarray query $[l,r]$, print any value that occurs exactly once in that subarray. Print 0 if no such value exists.

Input

The first line contains $n$, the second line the array, the third line $q$, followed by $q$ ranges $l,r$.

Output

For every query print 0 if no unique-occurrence value exists; otherwise print any valid value.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 5000$, number of queries $\le 5000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le5\cdot10^5$
• $1\le a_i\le5\cdot10^5$
• $1\le l\le r\le n$

Example

Input

6
1 1 2 3 2 4
2
2 6
1 2

Output

4
0

Explanation

In sample range [2,6], values 1,3,4 occur once, so 4 is valid. Range [1,2] is [1,1], hence the answer is 0.