Cho dãy ~A~ gồm ~N~ số nguyên được đánh số từ ~1~ đến ~N~. Xử lý ~Q~ truy vấn, truy vấn thứ ~i~ gồm ba số nguyên ~l_i, r_i, x_i~, yêu cầu tìm giá trị ~p~ (~l_i \le p \le r_i~) nhỏ nhất thỏa mãn ~A_p \neq x_i~.

Input

• Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 10^6~).
• Dòng thứ hai chứa ~N~ số nguyên của dãy ~A~ (~1 \le A_i \le 10^6~).
• Dòng tiếp theo chứa số nguyên ~Q~ (~1 \le Q \le 10^6~).
• ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~l_i, r_i, x_i~ (~1 \le l_i, r_i \le N~, ~1 \le x_i \le 10^6~).

Output

• Với mỗi truy vấn, in ra giá trị ~p~ trên một dòng. Nếu không có giá trị ~p~ phù hợp, in ra ~-1~.

Examples

Sample Input

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

Sample Output

3
1
-1
-1

Scoring

• Subtask ~1~ với ~30\%~ số điểm: ~N,Q \le 2000~
• Subtask ~2~ với ~30\%~ số điểm: ~N \le 2000~
• Subtask ~3~ với ~40\%~ số điểm: Không có ràng buộc gì thêm