第 2 题 股票行情 (stockquotes)

时间限制 10 s · 空间限制 256 MB · 59 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 stockquotes.in，输出文件 stockquotes.out。

• 题目代号：not
• 时间限制：10 s，内存限制：256 MB

题目描述

Bajtex 公司在 $N$ 天前在 Bajtocka 证券交易所发行了股票。为了吸引新的股东投资，公司除了强调股票能带来收益外，还想向潜在投资者展示股价一直在上涨。为此，他们决定挑选一个 $K$-区间——即连续 $K$ 天的行情，且股价在这 $K$ 天内严格上涨——来展示这些数据。现在他们想知道，对于不同的 $K$ 值，各有多少个这样的 $K$-区间。

例如，考虑 Bajtex 公司如下的股价：

第 1 … 10 天：4, 3, 5, 6, 7, 7, 4, 5, 6, 4（B$）。

• 若只看连续两天（2-区间），共有 5 种：(2, 3), (3, 4), (4, 5), (7, 8), (8, 9)。注意不能选 (5, 6)，因为股价没有上涨，只是持平。
• 若看连续三天（3-区间），共有 3 种：(2, 3, 4), (3, 4, 5), (7, 8, 9)。不能选 (1, 2, 3)，因为第 1 天到第 2 天出现了下跌。

你的任务是：对不同的 $K$，计算给定序列中的 $K$-区间个数。

输入格式

第一行一个自然数 $N$（$1 \le N \le 500\,000$），表示 Bajtex 公司上市的天数。

第二行包含 $N$ 个非负整数 $A_i$（$0 \le A_i \le 10^9$），以单个空格分隔，表示连续各天的股价。

第三行一个自然数 $Q$（$1 \le Q \le 500\,000$），表示询问数量。

接下来 $Q$ 行，每行一个自然数 $K_i$（$1 \le K_i \le N$），表示询问 $K_i$-区间的数量。

输出格式

输出 $Q$ 行，每行一个整数，第 $i$ 行表示 $K_i$-区间的数量。

样例

样例 1

输入：

10
4 3 5 6 7 7 4 5 6 4
5
2
3
1
4
5

输出：

5
3
10
1
0

样例 2

输入：

5
1 2 3 4 5
5
5
4
3
2
1

输出：

1
2
3
4
5

样例 3

输入：

10
1 1 2 2 3 3 4 4 5 5
4
3
2
10
1

输出：

0
4
0
10

样例 4

输入：

10
10 9 8 7 6 5 4 3 2 1
4
1
10
5
2

输出：

10
0
0
0

样例 5

输入：

10
1 2 3 4 5 1 2 3 4 5
5
3
2
5
10
4

输出：

6
8
2
0
4

其余样例：测试 not0f 中 $N = 500\,000$，行情为 $[1, 2, 3, \dots, 998, 999, 0]$ 重复 500 次，$Q = 500\,000$，第 $i$ 个询问问 $i$-区间的数量。

数据范围与子任务

完整数据满足 $1 \le N, Q \le 500\,000$。