Монокарп играет в компьютерную игру. В этой игре его персонаж — некромант. Он сражается с \(n\) монстрами, пронумерованными от \(1\) до \(n\). У каждого монстра есть два параметра: здоровье и сила.
Монокарп рассматривает \(q\) сценариев битвы. В каждом сценарии он выбирает некоторый отрезок \([l, r]\) монстров и вычисляет количество ходов, необходимых для победы над всеми этими монстрами.
Каждый сценарий проходит следующим образом. Сначала Монокарп убивает монстра \(l\) и воскрешает его в качестве зомби (это не считается ходом). Затем на каждом ходу происходит следующее: пусть \(i\) — индекс первого монстра в отрезке \([l, r]\), который все еще жив. Все зомби атакуют монстра \(i\), уменьшая его здоровье на суммарную силу зомби. После этого, если у монстра \(i\) остается \(0\) или меньше здоровья, он умирает, и Монокарп воскрешает его в качестве зомби.
Когда монстр воскрешается, сила зомби равна силе монстра.
Помогите Монокарпу для каждого сценария вычислить, сколько ходов потребуется, чтобы убить всех монстров в отрезке.