Khai thác gỗ

Khu rừng có $N$ cây gỗ quý với lượng gỗ dự kiến khai thác được lần lượt là $v_1,v_2,\dots ,v_N$. Có $P$ phương án khai thác được đưa ra, phương án thứ $i$ ($1\le i\le P$) đề xuất khai thác tất cả các cây có lượng gỗ từ $k_i$ trở lên ($1\le k_i\le {10}^6$, $1\le i\le P$).

Yêu cầu: Em hãy giúp ban quản lý rừng xác định tổng lượng gỗ khai thác được của mỗi phương án.

Dữ liệu vào

Dữ liệu vào gồm:

• Dòng đầu ghi số nguyên dương $N$ ($1<N\le {10}^6$);
• Dòng thứ hai ghi $N$ số nguyên $v_1,v_2,\dots ,v_N$ ($1\le v_j\le {10}^6$, $1\le j\le N$);
• Dòng thứ ba ghi số nguyên dương $P$ ($1\le P\le {10}^5$);
• Dòng cuối cùng ghi lần lượt $P$ số nguyên $k_1,k_2,\dots ,k_P$.

Dữ liệu ra

In ra $P$ dòng, mỗi dòng ghi lần lượt tổng lượng gỗ khai thác được tương ứng của từng phương án.

Ràng buộc

• $1<N\le {10}^6$.
• $1\le v_j\le {10}^6$.
• $1\le P\le {10}^5$.
• $1\le k_i\le {10}^6$.

Subtasks

• Subtask 1 ($40\%$ số điểm): $P=1$.
• Subtask 2 ($30\%$ số điểm): $2\le N,P\le 1000$.
• Subtask 3 ($30\%$ số điểm còn lại): không có ràng buộc gì thêm.

Ví dụ