差が D 以上のペアの個数 Bash(Beta)編（paizaランク A 相当）

部活で、実力の差が大きい部員どうしをペアにして特別なトレーニングをすることになりました。部員 N 人の実力スコアを昇順に並べた整数列 A_1, A_2, ..., A_N があります（A_1 ≦ A_2 ≦ ... ≦ A_N）。

顧問の先生は「どのくらいスコアが離れた 2 人を組ませるか」をまだ決めかねているため、Q 通りの基準 D_1, D_2, ..., D_Q を試すことにしました。

各クエリ D_q について、スコアの差が D_q 以上（A_j - A_i ≧ D_q、i < j）となる 2 人の組 (i, j) が何通りできるかを求め、その総数を出力してください。

各クエリの答えを、与えられた順に 1 行ずつ出力してください。

1 つのクエリについてすべての組を二重ループで調べると最大で約 N × N / 2 回の比較が必要になり、それを Q 回くり返すと間に合いません。各 i について「A_i + D_q 以上のスコアを持つ部員が最初に現れる位置」を二分探索で求めると、その位置から後ろにいる部員はすべて A_j - A_i ≧ D_q を満たすため、まとめて人数を数えられます。