Một lần xuất hiện (One Occurrence)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $a$ và nhiều truy vấn đoạn $[l,r]$. Với mỗi truy vấn, hãy in bất kỳ giá trị nào xuất hiện đúng một lần trong đoạn. Nếu không tồn tại giá trị như vậy, in 0.

Dữ liệu vào

Dòng đầu chứa $n$. Dòng thứ hai chứa dãy. Dòng thứ ba chứa $q$. Mỗi trong $q$ dòng sau chứa $l,r$.

Kết quả

Với mỗi truy vấn, in 0 nếu không có giá trị xuất hiện đúng một lần; ngược lại in bất kỳ một giá trị hợp lệ.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 5000$, số truy vấn $\le 5000$.
• Các điều kiện còn lại như 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$

Ví dụ

Input

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

Output

4
0

Giải thích

Trong đoạn [2,6] của mẫu, các giá trị 1,3,4 đều xuất hiện đúng một lần, nên 4 là một đáp án hợp lệ. Đoạn [1,2] là [1,1], nên phải in 0.