Василий очень хочет завести себе питомца. Еще с детства он мечтал иметь домашнего кузнечика. Василий подходит к выбору питомца очень ответственно, поэтому он хочет устроить кузнечику испытание!

Испытание Василия проходит на массиве $$$a$$$ длины $$$n$$$, который задает длины прыжков для каждой из $$$n$$$ клеток. Кузнечик может прыгать по клеткам по следующим правилам: с клетки с индексом $$$i$$$ он может прыгнуть в любую клетку с индексом от $$$i$$$ до $$$i+a_i$$$ включительно.

Назовем $$$k$$$-кузнечным числом некоторого массива минимальное количество прыжков, которое потребуется кузнечику, чтобы пропрыгать от первой клетки массива до последней, при этом до начала прыжков вы можете выбрать не более $$$k$$$ клеток и удалить их из массива. Когда клетка удаляется, остальные клетки перенумеровываются, однако величина $$$a_i$$$ для каждой клетки остается неизменной. При этом нельзя удалять первую и последнюю клетки массива.

Требуется обработать $$$q$$$ запросов следующего вида: даны три числа $$$l$$$, $$$r$$$, $$$k$$$, необходимо найти $$$k$$$-кузнечное число для массива, являющегося подотрезком массива $$$a$$$ с клетками от $$$l$$$ до $$$r$$$ включительно.