Xét dãy số nguyên dương ~a_1, a_2,...,a_n~, trong đó. Với mỗi truy vấn số nguyên x, hãy xác định số cặp ~(a_i,a_j)~ thỏa mãn các điều kiện: ~a_i+a_j \leq x (1 \leq i < j \leq n)~.

Input

• Dòng đầu tiên chứa số nguyên ~n~
• Dòng thứ hai chứa n số nguyên dương ~a_1,a_2,...,a_n(a_i \leq 10^9)~.
• Dòng thứ ba chứa số nguyên ~q~ – số lượng truy vấn trong file input
• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~x (x \leq2 \times 10^9)~

Output

• ~q~ dòng, mỗi dòng là số cặp tìm được tương ứng với số ~x~ theo thứ tự trong file input.

Scoring

• ~30%~ số test tương ứng ~30%~ số điểm có ~n \leq 10^3; q \leq 10; a_i \leq 10^6~.
• ~30%~ số test khác tương ứng ~30%~ số điểm có ~q,n \leq 2 \times 10^3;a_i \leq 10^6~.
• ~40%~ số test còn lại tương ứng ~40%~ số điểm có ~n \leq 5 \times 10^4;q \leq 2 \times 10^3~.

Sample Input

5
5 10 2 7 9
2
15
13

Sample Output

7
5