在 Byteotian 线形森林中，有 $n$ 棵树排成一排。一只小鸟停在第一棵树的顶端，想要飞到最后一棵树的顶端。由于这只鸟非常小，它可能没有足够的体力一次性飞到终点。如果鸟当前停在第 $i$ 棵树上，它可以在一次飞行中飞到第 $i+1, i+2, \dots, i+k$ 棵树中的任意一棵，然后必须休息。

此外，向上飞行比向下飞行要困难得多。如果一次飞行结束的树的高度不低于起飞的树的高度，那么这次飞行就是“费力”的。否则，这次飞行就不费力。

目标是选择小鸟落脚的树，使得整个飞行过程最不费力，即“费力”的飞行次数最少。我们注意到鸟类是群居动物，这只小鸟还有几位鸟朋友也想从第一棵树飞到最后一棵树。所有鸟的体力各不相同，因此这些鸟朋友的参数 $k$ 可能不同。请帮助所有大大小小的鸟儿！

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 1\,000\,000$)，表示 Byteotian 线形森林中树的数量。第二行包含 $n$ 个整数 $d_{1}, d_{2}, \dots, d_{n}$ ($1 \le d_{i} \le 10^{9}$)，由空格分隔，其中 $d_{i}$ 表示第 $i$ 棵树的高度。

第三行包含一个整数 $q$ ($1 \le q \le 25$)，表示需要规划飞行路线的鸟的数量。接下来的 $q$ 行描述这些鸟：第 $i$ 行包含一个整数 $k_{i}$ ($1 \le k_{i} \le n-1$)，表示第 $i$ 只鸟的体力。换句话说，第 $i$ 只鸟在必须休息前最多可以跨越的树的数量为 $k_{i}$。

在总分至少为 $l$ 的测试点中，$n \le 100\,000$。在总分至少为 $l$ 的子任务中，甚至满足 $n \le 1\,000$。

输出格式

程序应向标准输出打印 $q$ 行。第 $i$ 行应输出第 $i$ 只鸟最少需要的费力飞行次数。

样例

输入格式 1

9
4 6 3 6 3 7 2 6 5
2
2
5

输出格式 1

2
1

第一只鸟可以停在第 1, 3, 5, 7, 8, 9 棵树上。它的费力飞行次数为从第 3 棵树到第 5 棵树，以及从第 7 棵树到第 8 棵树的飞行。

样例评分测试

• 1ocen: $n=11$, $q=1$, $k_{1}=5$, 所有树高度相同，答案为 2（在第 6 棵树停一次即可）；
• 2ocen: $n=100$, $q=2$, $k_{1}=5$, $k_{2}=6$, 树高在 1 和 2 之间交替——对于两只鸟来说，每 5 棵树停一次是最优的，每只鸟都有 11 次费力飞行；
• 3ocen: $n=100$, $q=1$, $k_{1}=10$, 高度序列为：100, 99, …, 1，答案为 0；
• 4ocen: $n=1,000,000$, $q=25$, $k_{i}=i$, $d_{1000}=d_{2000}=d_{3000}=\dots=d_{1000000}=2$，其余树满足 $d_{i}=1$。