Василий очень хочет завести себе питомца. Еще с детства он мечтал иметь домашнего кузнечика. Василий подходит к выбору питомца очень ответственно, поэтому он хочет устроить кузнечику испытание!
Испытание Василия проходит на массиве \(a\) длины \(n\), который задает длины прыжков для каждой из \(n\) клеток. Кузнечик может прыгать по клеткам по следующим правилам: с клетки с индексом \(i\) он может прыгнуть в любую клетку с индексом от \(i\) до \(i+a_i\) включительно.
Назовем \(k\)-кузнечным числом некоторого массива минимальное количество прыжков, которое потребуется кузнечику, чтобы пропрыгать от первой клетки массива до последней, при этом до начала прыжков вы можете выбрать не более \(k\) клеток и удалить их из массива. Когда клетка удаляется, остальные клетки перенумеровываются, однако величина \(a_i\) для каждой клетки остается неизменной. При этом нельзя удалять первую и последнюю клетки массива.
Требуется обработать \(q\) запросов следующего вида: даны три числа \(l\), \(r\), \(k\), необходимо найти \(k\)-кузнечное число для массива, являющегося подотрезком массива \(a\) с клетками от \(l\) до \(r\) включительно.