A6975 | [POI 2014] PTA-Little Bird

## 数据范围

$1 \le n \le 10^6$，$1 \le d_i \le 10^9$，$1 \le q \le 25$，$1 \le k_i \le n - 1$。

## 样例解释

**树的高度序列：** 4, 6, 3, 6, 3, 7, 2, 6, 5 (索引 1 到 9)

---

**第一只鸟 ($k=2$)：**
* **目标：** 从第 1 棵树跳到第 9 棵树，每次跳跃距离 $\le 2$。
* **最优路径：** $1 \to 3 \to 5 \to 7 \to 9$
1. **$1 \to 3$** (高度 $4 \to 3$)：高度下降 ($4 > 3$)，**花费 0**。
2. **$3 \to 5$** (高度 $3 \to 3$)：高度不降 ($3 \le 3$)，**花费 1**。
3. **$5 \to 7$** (高度 $3 \to 2$)：高度下降 ($3 > 2$)，**花费 0**。
4. **$7 \to 9$** (高度 $2 \to 5$)：高度上升 ($2 \le 5$)，**花费 1**。
* **总劳累值：** $0 + 1 + 0 + 1 = \mathbf{2}$。

---

**第二只鸟 ($k=5$)：**
* **目标：** 从第 1 棵树跳到第 9 棵树，每次跳跃距离 $\le 5$。
* **最优路径：** $1 \to 6 \to 9$
1. **$1 \to 6$** (高度 $4 \to 7$)：可以直接跳 (距离 5)，高度上升 ($4 \le 7$)，**花费 1**。
2. **$6 \to 9$** (高度 $7 \to 5$)：可以直接跳 (距离 3)，高度下降 ($7 > 5$)，**花费 0**。
* **总劳累值：** $1 + 0 = \mathbf{1}$。