威廉真的很想养一只宠物。他从小就梦想养一只宠物蚱蜢。威廉对于选择宠物非常负责,所以他想为蚱蜢设立一个试验!
试验在长度为 $$$n$$$ 的数组 $$$a$$$ 上进行,该数组定义每个 $$$n$$$ 单元的跃点长度。蚱蜢可以根据以下规则在销售中跳跃:从索引为 $$$i$$$ 的单元格,它可以跳转到索引从 $$$i$$$ 到 $$$i+a_i$$$(含)的任何单元格。
让我们将某个数组的 $$$k$$$-grasshopper 值称为 Grasshopper 从第一个单元格跳到最后一个单元格所需的最小跳跃数,但在开始之前,您可以选择不超过 $$$k$$$ 单元格并将它们从数组中删除。删除某个单元格后,所有其他单元格都会重新编号,但每个单元格的 $$$a_i$$$ 值保持不变。在此期间,第一个和最后一个单元格可能不会被删除。
需要处理以下格式的 $$$q$$$ 查询:为您提供三个数字 $$$l$$$、$$$r$$$、$$$k$$$。您需要找到数组的 $$$k$$$-grasshopper 值,该数组是数组 $$$a$$$ 的子数组,元素从 $$$l$$$ 到 $$$r$$$(包含在内)。
输入
第一行包含两个整数$$$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)$$$),分别是子数组的边和grasshopper值的个数。
输出
对于每个查询,在新行中打印一个数字 - 对查询的响应。
示例
输入 #1
9 5 1 1 2 1 3 1 2 1 1 1 1 0 2 5 1 5 9 1 2 8 2 1 9 4
输出 #1
0 2 1 2 2
注意
对于第二个查询,过程如下所示:
对于第三个查询,过程如下所示: