P1074云间飞渡（flight）

【题目背景】

海图完成拼合后，船队顺利返回晨汐港。为了尽快把遗迹记录送往内陆，tfbz 选择了一条穿过云海的旧航路，并准备借助沿途高台完成一场飞渡。

【题目描述】

云海中有 $n$ 座高台，从起点到星门依次编号为 $1\sim n$，第 $i$ 座高台的高度为 $h_i$。tfbz 最初位于第 $1$ 座高台，需要到达第 $n$ 座高台。

一次飞渡可以从第 $j$ 座高台到达第 $i$ 座高台，其中 $j<i$。若 $h_j\leq h_i$，这次飞渡需要逆着上升气流前进，产生 $1$ 点疲劳。若 $h_j>h_i$，则可以顺着气流下降，不会产生疲劳。

航路记录中共有 $q$ 种风况。第 $x$ 种风况给出一个整数 $k_x$，在这种风况下，每次飞渡都必须满足 $i-j\leq k_x$。

每种风况相互独立。对于每种风况，请你求出 tfbz 从第 $1$ 座高台到达第 $n$ 座高台所需的最少疲劳。

形式化题意：给定长度为 $n$ 的序列 $\{h\}$ 与 $q$ 个整数 $k_x$，对于每个 $k_x$，求

其中 $[\cdot]$ 为 Iverson 括号。

【输入格式】

从文件 $\textbf{\textit{flight.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含一个非负整数 $c$ 与一个正整数 $T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含一个正整数 $n$，表示高台数量。

第二行包含 $n$ 个正整数 $h_1,h_2,\ldots,h_n$，表示各座高台的高度。

第三行包含一个正整数 $q$，表示风况数量。

接下来 $q$ 行，第 $x$ 行包含一个正整数 $k_x$，表示第 $x$ 种风况下单次飞渡能够跨过的最大编号距离。

【输出格式】

输出到文件 $\textbf{\textit{flight.out}}$ 中。

对于每组测试数据输出 $q$ 行，第 $x$ 行一个整数，表示第 $x$ 种风况下能够得到的最少疲劳。

【样例 1 输入】

10 22534 2 5 1 3435162748491 1 1 1102112123

【样例 1 输出】

1221304251

【说明/提示】

【样例 1 解释】

在第一组测试数据的第二种风况中，可以依次经过第 $1,3,5$ 座高台，也可以依次经过第 $1,2,4,5$ 座高台，两种路线都只产生 $1$ 点疲劳。

当 $k_x=4$ 时，可以从第 $1$ 座高台直接到达第 $5$ 座高台。由于 $h_1>h_5$，不会产生疲劳。

【样例 2】

见选手目录下的 $\textbf{\textit{flight/flight2.in}}$ 和 $\textbf{\textit{flight/flight2.ans}}$。

该组样例符合测试点 $1\sim 3$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{flight/flight3.in}}$ 和 $\textbf{\textit{flight/flight3.ans}}$。

该组样例符合测试点 $4\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{flight/flight4.in}}$ 和 $\textbf{\textit{flight/flight4.ans}}$。

该组样例符合测试点 $9\sim 11$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{flight/flight5.in}}$ 和 $\textbf{\textit{flight/flight5.ans}}$。

该组样例符合测试点 $12\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{flight/flight6.in}}$ 和 $\textbf{\textit{flight/flight6.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 10$，$2\leq n\leq 10^6$，$1\leq q\leq 25$，$1\leq h_i\leq 10^9$，$1\leq k_x<n$。对于同一个测试点，保证 $\sum nq\leq 2.5\times 10^7$。

特殊性质：对于同一个测试点，保证所有测试数据的 $n\sum_{x=1}^{q}k_x$ 之和不超过 $2\times 10^7$。