Cho một dãy số nguyên gồm ~n~ phần tử ~a_1, a_2,…,a_n~ đã được sắp xếp không giảm (các phần tử có thể bằng nhau) và một số nguyên ~k~.

Yêu cầu: Hãy cho biết:

1. Có hay không phần tử ~k~ trong dãy (YES/NO).
2. Chỉ số xuất hiện đầu tiên của khóa ~k~ trong dãy.
3. Chỉ số xuất hiện lần cuối của khóa ~k~ trong dãy.
4. Chỉ số của phần tử nhỏ nhất lớn hơn khóa ~k~.
5. Chỉ số của phần tử lớn nhất nhỏ hơn khóa ~k~.

Input

• Dòng ~1~ chứa số nguyên ~n~ (~2≤n≤2*10^5~).
• Dòng ~2~ chứa ~n~ số nguyên ~a_1, a_2,…,a_n~ (~|ai|≤2*10^9~).
• Dòng ~3~ chứa số nguyên dương ~m~ - là số truy vấn (~m<=10^5~).
• ~m~ dòng tiếp theo, mỗi dòng chứa ~2~ số: ~x~ và ~k~. Trong đó ~x =~ {~1,2,3,4,5~} - tương ứng với thứ tự yêu cầu trên, và ~k~ là khóa cần truy vấn (~|k|≤2*10^9~). Trường hợp không tồn tại chỉ số nào thỏa mãn thì in ra ~-1~.

Output

• Ứng với mỗi bộ test ghi ra các yêu cầu tường ứng như trên.

Sample Input

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

Sample Output

YES
6
-1
4
6