TRƯỜNG THPT CHUYÊN LÊ HỒNG PHONG NAM ĐỊNH

Cho mảng A gồm N số nguyên, và Q câu hỏi, câu hỏi thuộc một trong hai dạng sau:

0 x: nghĩa là có bao nhiêu số trong mảng A không nhỏ hơn x

1 x: nghĩa là có bao nhiêu số trong mảng A lớn hơn x

Input

Dòng đầu tiên gồm số nguyên dương N

Dòng thứ hai gồm N số nguyên của mảng A

Dòng thứ ba là số nguyên Q, biểu thị số lượng câu hỏi

Mỗi dòng trong Q dòng sau đó, biểu thị câu hỏi thuộc một trong hai kiểu nêu trên

Output

Với mỗi câu hỏi, đưa ra câu trả lời trên một dòng

Giới hạn:

1≤N≤10⁵
1≤Q≤ 3×10⁵
1≤ A[i], x ≤10⁹

Example

Input:
4
1 2 3 4
3
0 5
1 3
0 3

Output:
0
1
2