CF1523H.Hopping Around the Array

William really wants to get a pet. Since his childhood he dreamt about getting a pet grasshopper. William is being very responsible about choosing his pet, so he wants to set up a trial for the grasshopper!

The trial takes place on an array $a$ of length $n$, which defines lengths of hops for each of $n$ cells. A grasshopper can hop around the sells according to the following rule: from a cell with index $i$ it can jump to any cell with indices from $i$ to $i+a_i$ inclusive.

Let's call the $k$-grasshopper value of some array the smallest number of hops it would take a grasshopper to hop from the first cell to the last, but before starting you can select no more than $k$ cells and remove them from the array. When a cell is removed all other cells are renumbered but the values of $a_i$ for each cell remains the same. During this the first and the last cells may not be removed.

It is required to process $q$ queries of the following format: you are given three numbers $l$, $r$, $k$. You are required to find the $k$-grasshopper value for an array, which is a subarray of the array $a$ with elements from $l$ to $r$ inclusive.

威廉非常想养一只宠物。自童年起，他就梦想着养一只蚱蜢作为宠物。威廉在挑选宠物时非常负责任，因此他想为这只蚱蜢安排一次“试用期”！

这次试用期在一个长度为 $n$ 的数组 $a$ 上进行，该数组定义了每个单元格（共 $n$ 个）所对应的跳跃长度。蚱蜢可在这些单元格之间按如下规则跳跃：从下标为 $i$ 的单元格出发，它可以跳到任意一个下标在 $i$ 到 $i+a_i$（含端点）范围内的单元格。

我们定义某个数组的 $k$-蚱蜢值 为：蚱蜢从第一个单元格跳到最后一个单元格所需的最少跳跃次数；但在开始跳跃前，你最多可以从中移除 $k$ 个单元格。当某个单元格被移除后，其余单元格将重新编号（即下标连续），但每个单元格对应的 $a_i$ 值保持不变。注意：首尾两个单元格不可被移除。

现在需要处理 $q$ 个查询，每个查询给出三个整数 $l$、$r$、$k$。你需要计算数组 $a$ 的子数组（即下标从 $l$ 到 $r$（含端点）的所有元素构成的子数组）的 $k$-蚱蜢值。

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 20000$), the length of the array and the number of queries respectively.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) – the elements of the array.

The following $q$ lines contain queries: each line contains three integers $l$, $r$ and $k$ ($1 \le l \le r \le n$, $0 \le k \le min(30, r-l)$), which are the edges of the subarray and the number of the grasshopper value respectively.

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 20000$），分别表示数组的长度和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）—— 数组的元素。

接下来的 $q$ 行每行包含一个查询：每行包含三个整数 $l$、$r$ 和 $k$（$1 \le l \le r \le n$，$0 \le k \le \min(30, r-l)$），分别表示子数组的左右边界以及蚱蜢值的序号。

For each query print a single number in a new line — the response to a query.

对于每个查询，在新的一行中输出一个数字——该查询的答案。

For the second query the process occurs like this:

For the third query the process occurs like this:

对于第二个查询，过程如下所示：

对于第三个查询，过程如下所示：