样例下载

问题描述

为了准备狂欢节，奶牛 Bessie 准备买一些花来作为装饰。

有 $n$ 盆花排成一列，第 $i$ 盆花的价格是 $a_i$。Bessie 准备选择一个子区间的花进行购买，即对于 $1\le l\le r\le n$，她准备购买第 $l$ 盆，第 $r$ 盆和它们之间的所有花。如果 $l=r$，那么她只购买一盆花。换句话说，她一共有 $\frac{1}{2}n(n+1)$ 种购买花的方式。但是因为她的预算有限，因此 Bessie 希望购买的花的平均价格不超过 $k$。现在她想知道，有多少种满足要求的购买花的方式。

由于 Bessie 还没有确定预算，因此她可能会给你几个不同的 $k$，你需要对每一个 $k$ 分别给出答案。

输入格式

输入的第一行包含一个整数 $n$，代表花的数量。

之后一行包含 $n$ 个正整数，第 $i$ 个正整数 $a_i$ 代表第 $i$ 盆花的价格。

之后一行包含一个正整数 $m$，代表询问组数。

之后一行包含 $m$ 个正整数，每个正整数代表一次询问给出的 $k$。

输出格式

输出包含 $m$ 行，每行一个整数，表示一个询问的答案。

输入输出样例

输入

4
8 3 2 5
2
3 5

输出

3
8

数据规模与约定

对于 $20\%$ 的数据，$n\le 100$；

对于 $50\%$ 的数据，$n\le 1000$；

对于另外 $20\%$ 的数据，保证${a_i\le a_{i+1}}$；

对于 $100\%$ 的数据，$n\le100000$，$m\le 10$，$1\le a_i,k\le 10^9$。