Nam rất thích ăn kẹo mút nên ngày nào đi học cậu ta cũng đến các quán kẹo để tận hưởng những cảm giác ngọt ngào của những chiếc kẹo. Trong thành phố có n quán có bán kẹo mút với nhiều hương vị và giá thành khác nhau, giá bán ở quán thứ \(i\) là \(x_i\) \((1 \leq i \leq n)\). Nam lên kế hoạch mua kẹo trong \(q\) ngày tiếp theo, ngày thứ \(j\) \((1 ≤ j ≤ q)\) không được sử dụng quá số tiền \(t_j\) để mua kẹo.

Yêu cầu

Hãy xác định số lượng quán khác nhau Nam có thể đến mua kẹo trong ngày thứ \(j\).

Dữ liệu

• Dòng đầu ghi số nguyên dương \(n\ (1 \leq n \leq 10^6)\);
• Dòng thứ hai ghi \(n\) số nguyên dương \(x_1, x_2, ... , x_n\) \((1 ≤ x_i ≤ 100\,000\,000)\).
• Dòng thứ ba ghi số nguyên dương \(q\) \((1 ≤ q ≤ 100.000).\)
• Dòng thứ \(j\) trong \(q\) dòng tiếp theo ghi số nguyên \(t_j\) \((1 ≤ t_j ≤ 1\,000\,000\,000)\).

Kết quả

In ra \(q\) dòng, dòng thứ \(j\) ghi số lượng quán khác nhau mà ngày thứ \(j\) Nam có thể mua kẹo.

Ví dụ

Ghi chú

• Có 40% test có \(n, q ≤ 2000\) tương ứng 40% số điểm;
• Có 60% test có \(2000 < n ≤ 100.000\) tương ứng 60% số điểm